此前一天，一位MS的朋友邀我一起去與他讨論快速排序，紅黑樹，字典樹，B樹、字尾樹，包括KMP算法，唯獨在講解KMP算法的時候，言語磕磕盼盼，我想，原因有二：1、部落格内的東西不常回顧，忘了不少；2、便是我對KMP算法的了解還不夠徹底，自不用說講解自如，運用自如了。是以，特再寫本篇文章。由于此前，個人已經寫過關于KMP算法的兩篇文章，是以，本文名為：KMP算法之總結篇。
本文分為二個部分：第一部分、再次回顧普通的BF算法與KMP算法各自的時間複雜度，并兩相對照各自的比對原理；第二部分、通過我此前一篇文章的引用，用圖從頭到尾詳細闡述KMP算法中的next數組求法，并運用求得的next數組寫出KMP算法的源碼。力求讓此文徹底讓讀者洞穿此KMP算法，所有原理，來龍去脈，讓讀者搞個通通透透。
1、普通字元串比對BF算法與KMP算法的時間複雜度比較
KMP算法是一種線性時間複雜的字元串比對算法，它是對BF算法（Brute-Force，最基本的字元串比對算法的）改進。對于給的原始串S和模式串P，需要從字元串S中找到字元串P出現的位置的索引。
BF算法的時間複雜度O(strlen(S) * strlen(T))，空間複雜度O(1)。
KMP算法的時間複雜度O(strlen(S) + strlen(T))，空間複雜度O(strlen(T))。
2、BF算法與KMP算法的差別
假設現在S串比對到i位置，T串比對到j位置。那麼總的來說，兩種算法的主要差別在于失配的情況下，對
的值做的處理（注意，本文中的字元串下标都是從0開始計算）：
BF算法中，如果目前字元比對成功，即s[i+j] == T[j]，令j++，繼續比對下一個字元；如果失配，即S[i + j] != T[j]，需要讓i++,并且j= 0，即每次比對失敗的情況下，模式串T相對于原始串S向右移動了一位。
而KMP算法中，如果目前字元比對成功，即S[i]==T[j]，令i++，j++，繼續比對下一個字元；如果比對失敗，即S[i] != T[j]，需要保持i不變，并且讓j = next[j]，這裡next[j] <=j -1，即模式串T相對于原始串S向右移動了至少1位(移動的實際位數j - next[j] >=1),
同時移動之後，i之前的部分（即S[i-j+1 ~ i-1]），和j=next[j]之前的部分（即T[0 ~ j-2]）仍然相等。顯然，相對于BF算法來說，KMP移動更多的位數，起到了一個加速的作用！ (失配的特殊情形，令j=next[j]導緻j==0的時候，需要将i ++，否則此時沒有移動模式串)。
3、BF算法為什麼要回溯
首先說一下為什麼BF算法要回溯。如下兩字元串比對（恰如上面所述：BF算法中，如果目前字元比對成功，即s[i+j] == T[j]，令j++，繼續比對下一個字元）：
i+j（j随T中的j++變，而動）
S：aaaacefghij
j++
T：aaac
如果不回溯的話就是從下一位開始比起：
aaaacefghij
aaac
看到上面紅顔色的沒，如果不回溯的話，那麼從a 的下一位c 比起。然而下述這種情況就漏了（正确的做法當然是要回溯：如果失配，即S[i + j] != T[j]，需要讓i++,并且j= 0）：
aaac
是以，BF算法要回溯，其代碼如下：
int Index(SString S, SString T, int pos) {
//傳回T在S中第pos個字元之後的位置
i=pos; j=1;k=0;
while ( i< = S[0] && j< = T[0] ) {
if (S[i+k] = = T[j] ) {++k; ++j;} //繼續比較後續字元
else {i=i+1; j=1; k=0;} //指針回溯到 下一首位，重新開始
}
if(j>T[0]) return i; //子串結束，說明比對成功
else return 0;
}//Index
//傳回T在S中第pos個字元之後的位置
i=pos; j=1;k=0;
while ( i< = S[0] && j< = T[0] ) {
if (S[i+k] = = T[j] ) {++k; ++j;} //繼續比較後續字元
else {i=i+1; j=1; k=0;} //指針回溯到 下一首位，重新開始
}
if(j>T[0]) return i; //子串結束，說明比對成功
else return 0;
不過，也有特殊情況可以不回溯，如下：
abcdefghij(主串)
abcdefg(模式串)
即(模式串)沒有相同的才不需要回溯。
4、KMP 算法思想
普通的字元串比對算法必須要回溯。但回溯就影響了效率，回溯是由T串本身的性質決定的，是因為T串本身有前後'部分比對'的性質。像上面所說如果主串為abcdef這樣的，大沒有回溯的必要。
改進的地方也就是這裡，我們從T串本身出發，事先就找準了T自身前後部分比對的位置，那就可以改進算法。
如果不用回溯，那模式串下一個位置從哪裡開始呢？
還是上面那個例子，T(模式串)為ababc，如果c失配，那就可以往前移到aba最後一個a的位置，像這樣：
...ababd... ababc ->ababc
這樣i不用回溯，j跳到前2個位置，繼續比對的過程，這就是KMP算法所在。這個當T[j]失配後，j 應該往前跳的值就是j的next值，它是由T串本身固有決定的，與S串(主串)無關。
5、next數組的含義
重點來了。下面解釋一下next數組的含義，這個也是KMP算法中比較不好了解的一點。
令原始串為: S[i]，其中0<=i<=n；模式串為: T[j]，其中0<=j<=m。
假設目前比對到如下位置
S0,S1,S2,...,Si-j,Si-j+1...............,Si-1, Si, Si+1,....,Sn
T0,T1,...................,Tj-1, Tj, ..........
S和T的綠色部分比對成功，恰好到Si和Tj的時候失配，如果要保持i不變，同時達到讓模式串T相對于原始串S右移的話，可以更新j的值，讓Si和新的Tj進行比對，假設新的j用next[j]表示，即讓Si和next[j]比對，顯然新的j值要小于之前的j值，模式串才會是右移的效果，也就是說應該有next[j] <= j -1。那新的j值也就是next[j]應該是多少呢？我們觀察如下的比對：
1)如果模式串右移1位（從簡單的思考起，移動一位會怎麼樣），即next[j] = j - 1， 即讓藍色的Si和Tj-1比對 (注：省略号為未比對部分)
T0,T1,...................,Tj-1, Tj, .......... (T的劃線部分和S劃線部分相等【1】)
T0,T1,................Tj-2,Tj-1, ....... (移動後的T的劃線部分和S的劃線部分相等【2】)
根據【1】【2】可以知道當next[j] =j -1，即模式串右移一位的時候，有T[0 ~ j-2] == T[1 ~ j-1]。而這兩部分恰好是字元串T[0 ~j-1]的字首和字尾，也就是說next[j]的值取決于模式串T中j前面部分的字首和字尾相等部分的長度（好好揣摩這兩個關鍵字概念：字首、字尾，或者再想想，我的上一篇文章，從Trie樹談到字尾樹中，字尾樹的概念）。
2)如果模式串右移2位，即next[j] = j - 2， 即讓藍色的Si和Tj-2比對
S0,S1,...,Si-j,Si-j+1,Si-j+2...............,Si-1, Si, Si+1,....,Sn
T0,T1,T2,...................,Tj-1, Tj, ..........(T的劃線部分和S劃線部分相等【3】)
T0,T1,.............,Tj-3,Tj-2,.........(移動後的T的劃線部分和S的劃線部分相等【4】)
同樣根據【3】【4】可以知道當next[j] =j -2，即模式串右移兩位的時候，有T[0 ~ j-3] == T[2 ~ j-1]。而這兩部分也恰好是字元串T[0 ~j-1]的字首和字尾，也就是說next[j]的值取決于模式串T中j前面部分的字首和字尾相等部分的長度。
3)依次類推，可以得到如下結論：當發生失配的情況下，j的新值next[j]取決于模式串中T[0 ~ j-1]中字首和字尾相等部分的長度， 并且next[j]恰好等于這個最大長度。
為此，請再允許我引用上文中的一段原文：“KMP算法中，如果目前字元比對成功，即S[i]==T[j]，令i++，j++，繼續比對下一個字元；如果比對失敗，即S[i] != T[j]，需要保持i不變，并且讓j = next[j]，這裡next[j] <=j -1，即模式串T相對于原始串S向右移動了至少1位(移動的實際位數j - next[j] >=1),
同時移動之後，i之前的部分（即S[i-j+1 ~ i-1]），和j=next[j]之前的部分（即T[0 ~ j-2]）仍然相等。顯然，相對于BF算法來說，KMP移動更多的位數，起到了一個加速的作用！ (失配的特殊情形，令j=next[j]導緻j==0的時候，需要将i ++，否則此時沒有移動模式串)。”
于此，也就不難了解了我的關于KMP算法的第二篇文章之中：“當比對到S[i] != P[j]的時候有 S[i-j…i-1] = P[0…j-1]. 如果下面用j_next去比對，則有P[0…j_next-1] = S[i-j_next…i-1] = P[j-j_next…j-1]。此過程如下圖3-1所示。
當比對到S[i] != P[j]時，S[i-j…i-1] = P[0…j-1]：
S: 0 … i-j … i-1 i …
P: 0 … j-1 j …
如果下面用j_next去比對，則有P[0…j_next-1] = S[i-j_next…i-1] = P[j-j_next…j-1]。
是以在P中有如下比對關系（獲得這個比對關系的意義是用來求next數組）：
P: 0 … j-j_next .…j-1_ …
P: 0 … .j_next-1 …
是以，根據上面兩個步驟，推出下一比對位置j_next:
S: 0 … i-j … i-j_next … i-1 i …
P: 0 … j_next-1 j_next …
圖3-1 求j-next（最大的值）的三個步驟
下面，我們用變量k來代表求得的j_next的最大值，即k表示這S[i]、P[j]不比對時P中下一個用來比對的位置，使得P[0…k-1] = P[j-k…j-1]，而我們要盡量找到這個k的最大值。”。
根據上文的【1】與【2】的比對情況，可得第二篇文章之中所謂的k=1，根據上文的【3】與【4】的比對情況，k=2。
是以，歸根究底，KMP算法的本質便是：針對待比對的模式串的特點，判斷它是否有重複的字元，進而找到它的字首與字尾，進而求出相應的Next數組，最終根據Next數組而進行KMP比對。
6、Next數組的具體求法
上面給出了next數組的含義，下面給出求這個數組的具體算法。
1）顯然有next[0] = 0,next[1] = 0；
2）觀察【1】【2】可以看到如果T[j]==T[j -1]即T[j] == T[next[j]]的情況下(一定要注意 next[j]比j 小，有助于理清思路)，j+1前面字元串的字首和字尾的相等部分長度增加了1，是以有T[j]==T[next[j]]的時候，next[j+1] = next[j ] + 1;
同樣觀察【3】【4】也可以看到如果T[j]==T[j-2]亦即T[j]==T[next[j]的情況下，j+1前面的字元串的字首和字尾相等部分的長度增加了1，是以也有T[j]==T[next[j]]的時候，next[j+1] = next[j] + 1;
綜合上面的規律有當T[j] == T[next[j]]的情況下next[j+1]=next[j] + 1;
3) 當T[j] != T[next[j]]的情況next[j+1]又該等于多少呢？拿【1】【2】來說，如果此時T[j] != T[j-1]，可以移動【2】對應的串，直到【1】中的Tj等于下面【2】中對應的字元，此時就找到了j+1的最大前字尾。
注意，移動的時候同樣可以用到已經計算出的next數組的值。接下來，進入本文的第二部分。
本部分引自個人此前的關于KMP算法的第二篇文章：六之續、由KMP算法談到BM算法。前面，我們已經知道即不能讓P[j]=P[next[j]]成立成立。不能再出現上面那樣的情況啊！即不能有這種情況出現：P[3]=b，而竟也有P[next[3]]=P[1]=b。
正如在第二篇文章中，所提到的那樣：“這裡讀者了解可能有困難的是因為文中，時而next，時而nextval，把他們的思維搞混亂了。其實next用于表達數組索引，而nextval專用于表達next數組索引下的具體各值，差別細微。至于文中說不允許P
=P[next[j] ]出現，是因為已經有P
=b與S
比對敗，而P[next
]=P1=b，若再拿P[1]=b去與S
比對則必敗。”--六之續、由KMP算法談到BM算法。
又恰恰如上文中所述：“模式串T相對于原始串S向右移動了至少1位(移動的實際位數j - next[j] >=1)”。
ok，求next數組的get_nextval函數正确代碼如下：
//代碼4-1
//修正後的求next數組各值的函數代碼
void get_nextval(char const* ptrn, int plen, int* nextval)
{
int i = 0;
nextval[i] = -1;
int j = -1;
while( i < plen-1 )
{
if( j == -1 || ptrn[i] == ptrn[j] ) //循環的if部分
{
++i;
++j;
//修正的地方就發生下面這4行
if( ptrn[i] != ptrn[j] ) //++i，++j之後，再次判斷ptrn[i]與ptrn[j]的關系
nextval[i] = j; //之前的錯誤解法就在于整個判斷隻有這一句。
else
nextval[i] = nextval[j];
}
else //循環的else部分
j = nextval[j];
}
}
//代碼4-1
//修正後的求next數組各值的函數代碼
void get_nextval(char const* ptrn, int plen, int* nextval)
{
int i = 0;
nextval[i] = -1;
int j = -1;
while( i < plen-1 )
if( j == -1 || ptrn[i] == ptrn[j] ) //循環的if部分
++i;
++j;
//修正的地方就發生下面這4行
if( ptrn[i] != ptrn[j] ) //++i，++j之後，再次判斷ptrn[i]與ptrn[j]的關系
nextval[i] = j; //之前的錯誤解法就在于整個判斷隻有這一句。
else
nextval[i] = nextval[j];
else //循環的else部分
j = nextval[j];
舉個例子，舉例說明下上述求next數組的方法。 S a b a b a b c P a b a b c S[4] != P[4] 那麼下一個和S[4]比對的位置是k=2(也即P[next[4]])。此處的k=2也再次佐證了上文第3節開頭處關于為了找到下一個比對的位置時k的求法。上面的主串與模式串開頭4個字元都是“abab”，是以，比對失效後下一個比對的位置直接跳兩步繼續進行比對。 P a b a b c 比對成功 P的next數組值分别為-1 0 -1 0 2 next數組各值怎麼求出來的呢?分以下五步： 初始化：i=0，j=-1，由于j == -1，進入上述循環的if部分，++i得i=1，++j得j=0，且ptrn[i] != ptrn[j]（即a！=b）），是以得到第二個next值即nextval[1] = 0；； i=1，j=0，進入循環esle部分，j=nextval[j]=nextval[0]=-1； 進入循環的if部分，++i，++j，i=2，j=0，因為ptrn[i]=ptrn[j]=a,是以nextval[2]=nextval[0]=-1； i=2, j=0, 由于ptrn[i]=ptrn[j],再次進入循環if部分，是以++i=3，++j=1,因為ptrn[i]=ptrn[j]=b,是以nextval[3]=nextval[1]=0； i=3,j=1,由于ptrn[i]=ptrn[j]=b,是以++i=4，++j=2,退出循環。
這樣上例中模式串的next數組各值最終應該為:
圖4-1 正确的next數組各值
next數組求解的具體過程如下：
初始化：nextval[0] = -1，我們得到第一個next值即-1.
圖4-2 第一個next值即-1
i = 0，j = -1，由于j == -1，進入上述循環的if部分，++i得i=1，++j得j=0，且ptrn[i] != ptrn[j]（即a！=b）），是以得到第二個next值即nextval[1] = 0；
圖4-3 第二個next值0
上面我們已經得到，i= 1，j = 0，由于不滿足條件j == -1 || ptrn[i] == ptrn[j]，是以進入循環的esle部分，得j = nextval[j] = -1；此時，仍滿足循環條件，由于i = 1，j = -1，因為j == -1，再次進入循環的if部分，++i得i=2，++j得j=0，由于ptrn[i] == ptrn[j]（即ptrn[2]=ptrn[0]，也就是說第1個元素和第三個元素都是a），是以進入循環if部分内嵌的else部分，得到nextval[2] = nextval[0] = -1；
圖4-4 第三個next數組元素值-1
i = 2，j = 0，由于ptrn[i] == ptrn[j]，進入if部分，++i得i=3，++j得j=1，是以ptrn[i] == ptrn[j]（ptrn[3]==ptrn[1]，也就是說第2個元素和第4個元素都是b），是以進入循環if部分内嵌的else部分，得到nextval[3] = nextval[1] = 0；
圖4-5 第四個數組元素值0
如果你還是沒有弄懂上述過程是怎麼一回事，請現在拿出一張紙和一支筆出來，一步一步的畫下上述過程。相信我，把圖畫出來了之後，你一定能明白它的。
然後，我留一個問題給讀者，為什麼上述的next數組要那麼求?有什麼原理麼?
提示：我們從上述字元串abab 各字元的next值-1 0 -1 0，可以看出來，根據求得的next數組值，偷用字首、字尾的概念，一定可以判斷出在abab之中，字首和字尾相同，即都是ab，反過來，如果一個字元串的字首和字尾相同，那麼根據字首和字尾依次求得的next各值也是相同的。
5、利用求得的next數組各值運用Kmp算法
Ok，next數組各值已經求得，萬事俱備，東風也不欠了。接下來，咱們就要應用求得的next值，應用KMP算法來比對字元串了。還記得KMP算法是怎麼一回事嗎?容我再次引用下之前的KMP算法的代碼，如下：
//代碼5-1
//int kmp_seach(char const*, int, char const*, int, int const*, int pos) KMP模式比對函數
//輸入：src, slen主串
//輸入：patn, plen模式串
//輸入：nextval KMP算法中的next函數值數組
int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)
int i = pos;
int j = 0;
while ( i < slen && j < plen )
if( j == -1 || src[i] == patn[j] )
else
j = nextval[j];
//當比對失敗的時候直接用p[j_next]與s[i]比較，
//下面闡述怎麼求這個值，即比對失效後下一次比對的位置
if( j >= plen )
return i-plen;
else
return -1;
//代碼5-1
//int kmp_seach(char const*, int, char const*, int, int const*, int pos) KMP模式比對函數
//輸入：src, slen主串
//輸入：patn, plen模式串
//輸入：nextval KMP算法中的next函數值數組
int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)
int i = pos;
int j = 0;
while ( i < slen && j < plen )
if( j == -1 || src[i] == patn[j] )
//當比對失敗的時候直接用p[j_next]與s[i]比較，
//下面闡述怎麼求這個值，即比對失效後下一次比對的位置
if( j >= plen )
return i-plen;
return -1;
我們上面已經求得的next值，如下：
圖5-1 求得的正确的next數組元素各值
以下是比對過程，分三步：
第一步：主串和模式串如下，S[3]與P[3]比對失敗。
圖5-2 第一步，S[3]與P[3]比對失敗
第二步：S[3]保持不變，P的下一個比對位置是P[next[3]]，而next[3]=0,是以P[next[3]]=P[0]，即P[0]與S[3]比對。在P[0]與S[3]處比對失敗。
圖5-3 第二步，在P[0]與S[3]處比對失敗
第三步：與上文中第3小節末的情況一緻。由于上述第三步中，P[0]與S[3]還是不比對。此時i=3,j=nextval[0]=-1,由于滿足條件j==-1，是以進入循環的if部分,++i=4,++j=0,即主串指針下移一個位置，從P[0]與S[4]處開始比對。最後j==plen，跳出循環，輸出結果i-plen=4(即字串第一次出現的位置），比對成功，算法結束。
圖5-4 第三步，比對成功，算法結束
是以，綜上，總結上述三步為：
開始比對，直到P[3]！=S[3]，比對失敗；
nextval[3]=0，是以P[0]繼續與S[3]比對，再次比對失敗；
nextval[0]=-1，滿足循環if部分條件j==-1，是以，++i，++j，主串指針下移一個位置，從P[0]與S[4]處開始比對，最後j==plen，跳出循環，輸出結果i-plen=4，算法結束。
OK， 相信，看過此文後，無論是誰，都一定可以把KMP算法搞懂了（但萬一還是有讀者沒有搞懂，那怎麼辦呢？還有最後一個辦法：把本文列印下來，再仔細琢磨。如果是真真正正想徹底弄懂某一個東西，那麼必須付出些代價。但萬一要是列印下來了卻還是沒有弄懂呢？那來北京找我吧，我手把手教你。祝好運）。謝謝，完。
July、二零一一年十二月五日中午。