KMP演算法是眾多優秀的模式串匹配演算法中較早誕生的一個，也是相對最為人所知的一個。 演算法實現簡單，運行效率高，時間複雜度為O（n+m）（n和m分別為目標串和模式串的長度），比蠻力演算法的O（nm）快了許多。 理解KMP演算法，關鍵是理解其中的精髓——next[]數組。 （統一起見，下文將目標字元串記作ob ...
KMP演算法是眾多優秀的模式串匹配演算法中較早誕生的一個，也是相對最為人所知的一個。
演算法實現簡單，運行效率高，時間複雜度為O（n+m）（n和m分別為目標串和模式串的長度），比蠻力演算法的O（nm）快了許多。
理解KMP演算法，關鍵是理解其中的精髓——next[]數組。
（統一起見，下文將目標字元串記作obj，將模式字元串記作pattern，這與後面的程式代碼是一致的）
我們給一個字元串S定義一個next值，記作next(S)，next(S)=n表示：
（1）S的前n個字元構成的首碼，和後n個字元的尾碼是相等的
（2）n是滿足（1）條件的極大值。
如果不存在一個滿足（1）條件的n，那麼記next(S)=0。
例如，字元串“GACC”的next值為0，“GACCGG”的next值為1（極大前（後）綴為“G"），
“GACCGGACC”的next值為4（極大前（後）綴為”GACC“），“GAGAG”的next值為5。（極大前（後）綴就是它本身）。
而next[]數組，記錄的則是pattern的所有首碼的next值。
next數組的作用，就是在模式匹配的過程中，儘可能減少模式串的偏移量。
下令obj=”GACGAACGACCGACGACGCCGACGAC“（O__O"…），pattern=”GACGCCG“。
模式匹配的流程如下：
設立兩個”游標“i和j，分別指向obj串和pattern串當前正在檢查的字元，初始時令i=j=0。
首先檢查第一個字元，若obj[i]==pattern[j]，那麼i++，j++。直到遇到obj[i]！=pattern[j]的情形。
GACGAACGACCGACGACGCCGACGAC
GACGCCG
前4個字元檢查通過，但第5個字元（i=j=4）出了問題。
朴素的做法是讓i和j都回退，對於此例，回退至i=1，j=0，然而這樣無疑會做許多重覆的計算。
而KMP演算法的做法則是：只移動pattern。而移動的方法，則關係到演算法的效率甚至正確性。
我們的原則是：保證正確的前提下，使得重覆判斷的次數儘可能少。
最佳的做法是將j移動到next[j-1]的位置。
（1）由next的性質（首碼等於尾碼的極大值）可知，這樣可以省去儘可能多的判斷
（2）並且可以保證這樣做是正確的
此時j=4，而next[j-1]=next[3]=1，所以令j=1，再次進行比較。
GACGAACGACCGACGACGCCGACGAC
------GACGCCG
比對通過。令i=5，j=2。
GACGAACGACCGACGACGCCGACGAC
------GACGCCG
next[1]=0，所以令j=0。
GACGAACGACCGACGACGCCGACGAC
----------GACGCCG
即使回退到第一位也沒有出現字元相等的情形。而我們已經無法回退了。
此時只能令i++，表示前面的部分檢查無果，繼續向後檢查。
（你也可以理解成，讓obj相對於pattern運動）
GACGAACGACCGACGACGCCGACGAC
--------------GACGCCG
重覆上述的過程到了這裡（i=10，j=3），next[2]=0
GACGAACGACCGACGACGCCGACGAC
--------------------GACGCCG
pattern無法回退了，所以向前檢查。
GACGAACGACCGACGACGCCGACGAC
----------------------GACGCCG
i=15，j=4，next[3]=1
GACGAACGACCGACGACGCCGACGAC
----------------------------GACGCCG
回退之後比對成功，i++，j++，重覆這一過程，直到……
GACGAACGACCGACGACGCCGACGAC
----------------------------GACGCCG
至此我們便利用next數組完成了模式串匹配的過程。
可以看到，next數組使得匹配過程中少了很多不必要的計算，整個匹配過程顯得高效利落。
那麼問題來了，怎樣高效地求next數組？暴力是肯定行不通的。
事實上，next數組的求法和上述KMP演算法的步驟驚人地相似，甚至可以說，求next數組的過程就是一個自我匹配的過程。
也就是：求next[j]，就是讓pattern[0..j]和pattern[0..x]進行上述的匹配過程。這裡x=next[j-1]。next[j]=能夠匹配成功的子串的最大長度。
下令pattern=”GACCGGACCGA“
首先令next[0]=0，易知next[1]=0。
之後，由於pattern[2]！=pattern[0]，所以next[2]=0。同理next[3]=0。
由於pattern[4]==pattern[0]，所以next[4]=0+1=1。
這裡的0是next[3]的值。表示字元pattern[4]可以接到next[3]對應的尾碼之後。
由於pattern[5]！=pattern[1]，pattern[5]==pattern[next[0]]==pattern[0]，所以next[5]=1。
詳情如下：
GACCGG
--------GA 【 用pattern[0..1]匹配pattern[0..5]，這裡的1是next[4] 】
匹配不通過，所以令”模式串“的游標移至next[1]=0處（加了引號是因為這裡的”模式串“是對pattern本身進行匹配）
GACCGG
----------GA
類似地，可得：next[6]=next[5]+1=2，next[7]=next[6]+1=3，next[8]=next[7]+1=4，next[9]=next[8]+1=5。
next[10]的求法如下：
GACCGGACCGA
----------GACCGG 【 next[4]=1 】
GACCGGACCGA
------------------GACCGG
故next[10]=2。
代碼如下：
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxL=1000005; 5 6 char obj[maxL]; 7 char pattern[maxL]; 8 9 void input() 10 { 11 scanf("%s%s",obj,pattern); 12 } 13 14 int next[maxL]={0}; 15 16 int getNext() 17 { 18 next[0]=0; 19 int len=strlen(pattern); 20 for(int i=1;i<len;i++) 21 { 22 int k=next[i-1]; 23 while(k>=0 && pattern[i] != pattern[k]) k=k?next[k-1]:-1; 24 next[i]=k+1; 25 } 26 return len; 27 } 28 29 int kmp() //searching for the first place that pattern appears in obj 30 { 31 int lenObj=strlen(obj); 32 int lenPattern=getNext(); 33 for(int i=0,j=0;i<lenObj;i++) 34 { 35 while(j>=0 && obj[i] != pattern[j]) j=j?next[j-1]:-1; 36 if(lenPattern==(++j)) return i-j+1; 37 } 38 return -1; //not found 39 } 40 41 int main() 42 { 43 input(); 44 printf("%d\n",kmp()); 45 return 0; 46 }View Code
（我們用-1作為迴圈終止的條件）
附一道簡單的練習題，求pattern在obj中出現的次數。
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxL=1000005; 5 6 char obj[maxL]; 7 char pattern[maxL]; 8 9 void input() 10 { 11 scanf("%s%s",pattern,obj); 12 } 13 14 int next[maxL]={0}; 15 16 int getNext() 17 { 18 next[0]=0; 19 int len=strlen(pattern); 20 for(int i=1;i<len;i++) 21 { 22 int k=next[i-1]; 23 while(k>=0 && pattern[i] != pattern[k]) k=k?next[k-1]:-1; 24 next[i]=k+1; 25 } 26 return len; 27 } 28 29 int kmp() 30 { 31 int ans=0; 32 int lenObj=strlen(obj); 33 int lenPattern=getNext(); 34 for(int i=0,j=0;i<lenObj;i++) 35 { 36 while(j>=0 && obj[i] != pattern[j]) j=j?next[j-1]:-1; 37 if(lenPattern==(++j)) { ++ans; j=next[j-1]; } 38 } 39 return ans; 40 } 41 42 int main() 43 { 44 int T; scanf("%d",&T); 45 while(T--) 46 { 47 input(); 48 printf("%d\n",kmp()); 49 } 50 return 0; 51 }Problem：POJ P3461
演算法這東西，難者不會，會者不難。如果理解時遇到了瓶頸，不妨用筆實驗一下，總結規律，也許就能悟出演算法的思想。
ps.推薦另一篇博文：http://blog.csdn.net/OIljt12138/article/details/51107585，可以作為閱讀本文的對照參考
