摘要：KMP算法是字符串匹配的經(jīng)典算法，由于其O(m+n)的時間復(fù)雜度，至今仍被廣泛應(yīng)用。大道至簡，KMP算法非常簡潔，然而，其內(nèi)部卻蘊含著玄妙的理論，以至許多人知其然而不知其所以然。本文旨在解開KMP算法的內(nèi)部玄妙所在，希望能夠有助于學(xué)習(xí)與理解。

1、KMP算法
一種改進的字符串匹配算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發(fā)現(xiàn)，因此稱之為KMP算法。此算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配操作，其基本思想是：每當(dāng)匹配過程中出現(xiàn)字符串比較不等時，不需回溯指針，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右“滑動”盡可能遠的一段距離，繼續(xù)進行比較。

2、基于有限自動機理解算法
KMP 算法看似簡單，其實要完全理解還是有困難的。KMP算法其實可以看成是一個有限自動機，分為 2 部分：第一部分自動機的構(gòu)造 ( 對應(yīng)一般的說法就是失效函數(shù)，轉(zhuǎn)移函數(shù)， overlap 函數(shù) ) ，第二部分在自動機上搜索過程。舉個例子： 目標(biāo)串 T = acabaabaabcacaabc; 模式串 P=abaabcac ；根據(jù)模式串構(gòu)造自動機，向前的箭頭表示搜索前進的方向。向后的箭頭表示不匹配的回溯，即失效函數(shù)，或者狀態(tài)變遷函數(shù)。例如：
f(j=1) = 0;
f(j=2) = 0;
f(j=3) = 1;
f(j=4) = 1;
f(j=5) = 2;
f(j=6) = 0;
f(j=7) = 1;

KMP本質(zhì)上是構(gòu)造了DFA并進行了模擬，因此很顯然一旦從模版T構(gòu)造了自動機D，用D去匹配主串S的過程就是線性的。KMP最引人入勝的地方就在于構(gòu)造D的自匹配過程，它充分利用了D是一個DAG的性質(zhì)，使得構(gòu)造過程也是線性的。KMP算法不需要計算變遷函數(shù)，只用到輔助數(shù)組Next，即模式串自身的特征向量。特征向量可以用模式與其自身進行比較，預(yù)先計算出來，它可用于加快字符串匹配算法與有限自動機匹配器的執(zhí)行速度。

3、Next特征數(shù)組構(gòu)造
模式串P開頭的任意個字符，把它稱為前綴子串，如p0p1p2…pm-1。在P的第i位置的左邊，取出k個字符，稱為i位置的左子串，即pi-k+1... pi-2 pi-1 pi。求出最長的（最大的k）使得前綴子串與左子串相匹配稱為，在第i位的最長前綴串。第i位的最長前綴串的長度k就是模板串P在位置i上的特征數(shù)n[i]特征數(shù)組成的向量稱為該模式串的特征向量。
可以證明對于任意的模式串p=p0p1…pm-1,確實存在一個由模式串本身唯一確定的與目標(biāo)串無關(guān)的數(shù)組next，計算方法為：
(1) 求p0…pi-1中最大相同的前綴和后綴的長度k;
(2) next[i] = k;

作為特殊情況，當(dāng)i=0時，令next[i] = -1;顯然，對于任意i(0≤i<m)，有next[i] < i;假定已經(jīng)計算得到next[i], 那么next[i+1] = ? 特征數(shù)ni ( -1≤ ni ≤ i )是遞歸定義的，定義如下：
(1) n[0] ＝ -1，對于i > 0的n[i] ，假定已知前一位置的特征數(shù) n[i-1]＝ k ；
(2) 如果pi ＝ pk ，則n[i] ＝ k＋1 ；
(3) 當(dāng)pi ≠ pk 且k≠0時，則令k ＝ n [k -1] ; 讓(3)循環(huán)直到條件不滿足；
(4) 當(dāng)qi ≠ qk 且k ＝ 0時，則ni ＝ 0;

根據(jù)以上分析，可以得到Next特征數(shù)組的計算方法，算法代碼如下：
void get_next(SString T, int &next[]) { //求模式串T的next函數(shù)值并存入數(shù)組next i = 1; next[1] = 0; j = 0; while (i < T[0]) { if(j ==0 || T[i] == T[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } }

文獻[5]中解釋了以上計算方法存在一定缺陷，存在多比較的情況，可對其進行修正，得到如下算法：

void get_next(SString T, int &next[]) { //求模式串T的next函數(shù)值并存入數(shù)組next i = 1; next[1] = 0; j = 0; while (i < T[0]) { if(j ==0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) next[i] = j; else next[i] = next[j]; } else { j = next[j]; } } }

4、算法實現(xiàn)
KMP算法的難點就是有限自動機的構(gòu)造和特征向量的計算。解決了這兩個問題后，具體匹配算法就很簡單了。

int Index_KMP(SString S,SString T,int pos){
//利用模式串T的next函數(shù)求T在主串S中第pos個字符之后的位置的KMP算法。
//其中，T非空，1≤pos≤StrLength(S)。
i=pos; j=1;
while(i <= S[0] && j<= T[0]){
if(j == 0 || S[i] == T[j]) { ++i; ++j; }//繼續(xù)比較后繼字符
else j = next[j];//模式串象右移動
}
if(j>T[0]) return i-T[0];//匹配成功
else return 0;
}//Index_KMP

算法相關(guān)理論分析與證明，以及算法復(fù)雜性分析，若感興趣請參考文獻[3]、[4]、[5]，這里不再贅述。

5、參考文獻
[1] http://wansishuang.javaeye.com/blog/402018
[2] http://richardxx.yo2.cn/articles/kmp 和extend-kmp算法.html
[3] KMP算法講義PPT(Hu Junfeng, Peking University)
[4] 算法導(dǎo)論(第32章 字符串匹配)
[5] 數(shù)據(jù)結(jié)構(gòu)(第4章 串)

KMP算法深度解析