背景簡介：KMP算法用來處理字符串匹配的。給你A,B兩個字符串，檢查B串是否是A串的子串，類似于Java的String.indexOf("")。之所以叫做KMP，是因為這個算法是由Knuth、Morris、Pratt三個提出來的，取了這三個人的名字的頭一個字母。
原理介紹：找到匹配失敗時的最合適的回退位置，而不是簡單的回退到子串的第一個字符（常規(guī)的枚舉查找方式，是簡單的回退到子串的第一個字符，接下來準備寫一篇KMP算法的性能分析Java實現(xiàn)實例），即可提高查找的效率。因此為了找到這個合適的位置，先對子串預處理，從而得到一個回退位置的數(shù)組。過多的理論就不介紹了。
總體而言比較簡單，KMP算一個經(jīng)典的算法例子，很多筆試、面試也會問起?，F(xiàn)總結一下，放在這里供大家參考、交流，希望對大家有所幫助，下面直接給出實現(xiàn)例子，測試與分析也包含其中。
一、一個文件源代碼
KMP.java
源代碼為：
package algorithm.kmp;
/**
* KMP算法的Java實現(xiàn)例子與測試、分析
* @author 崔衛(wèi)兵
* @date 2009-3-25
*/
public class KMP {
/**
* 對子串加以預處理，從而找到匹配失敗時子串回退的位置
* 找到匹配失敗時的最合適的回退位置，而不是回退到子串的第一個字符，即可提高查找的效率
* 因此為了找到這個合適的位置，先對子串預處理，從而得到一個回退位置的數(shù)組
* @param B，待查找子串的char數(shù)組
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循環(huán)一次，就會找到一個回退位置
for(int i=1;i
//當找到第一個匹配的字符時，即j>0時才會執(zhí)行這個循環(huán)
//或者說p2中的j++會在p1之前執(zhí)行（限于第一次執(zhí)行的條件下）
//p1
while(j>0 %26amp;%26amp; B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有當子串中含有重復字符時，回退的位置才會被優(yōu)化
if(B[j]==B[i]){
j++;
}
//找到一個回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}
/**
* KMP實現(xiàn)
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i
//當找到第一個匹配的字符時，即j>0時才會執(zhí)行這個循環(huán)
//或者說p2中的j++會在p1之前執(zhí)行（限于第一次執(zhí)行的條件下）
//p1
while(j>0 %26amp;%26amp; B[j]!=A[i]){
//找到合適的回退位置
j=P[j-1];
}
//p2 找到一個匹配的字符
if(B[j]==A[i]){
j++;
}
//輸出匹配結果，并且讓比較繼續(xù)下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}
public static void main(String[] args) {
//回退位置數(shù)組為P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!這個會匹配1次","abcdef");
//回退位置數(shù)組為P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!這個會匹配2次","ititit");
//回退位置數(shù)組為P[0, 0, 0]
kmp("測試漢字的匹配，崔衛(wèi)兵。這個會匹配1次","崔衛(wèi)兵");
//回退位置數(shù)組為P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("這個會匹配0次","it1it1it1");
}
}
二、輸出結果
Find subString 'abcdef' at 16
Totally found 1 times for 'abcdef'.
Find subString 'ititit' at 11
Find subString 'ititit' at 24
Totally found 2 times for 'ititit'.
Find subString '崔衛(wèi)兵' at 8
Totally found 1 times for '崔衛(wèi)兵'.
Totally found 0 times for 'it1it1it1'.
三、總結
總體而言，KMP算法通過找到合適的回退位置從而可以提高匹配效率，但是如果匹配位置都是第一個字符呢？例如測試代碼中的
//回退位置數(shù)組為P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!這個會匹配2次","abcdef");
接下來準備寫一篇KMP算法的性能分析Java實現(xiàn)實例，下文再見。^_^