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作為循環終止的條件）
附一道簡單的練習題，求pattern在obj中出現的次數。
算法這東西，難者不會，會者不難。如果理解時遇到了瓶頸，不妨用筆實驗一下，總結規律，也許就能悟出算法的思想。
ps.推薦另一篇博文：http://blog.csdn.net/OIljt12138/article/details/51107585，可以作為閱讀本文的對照參考
