KMP是一種著名的字元串模式比對算法，它的名稱來自三個發明人的名字。這個算法的一個特點就是，在比對時，主串的指針不用回溯，整個比對過程中，隻需要對主串掃描一遍就可以了。是以适合對大字元串進行比對。
搜了網上很多KMP的代碼下來調試，發現不是下标越界，就是死循環的，相當詭異...最後重新拿起嚴老師那本《資料結構》來翻，各種費解，有個地方用下标值和字元串下标0的元素做判斷，更是詭異了...
過了一天，忽然覺悟了。網上這些代碼都是來自《資料結構》或者和他同源的版本的，而它使用的是以下标1為起始的字元串！對這種字元串組織格式，下标0存放的是字元串的長度。
可是如今主流的語言，幾乎都是用的下标0作為起始，書本上的代碼顯然沒法用，那就自己重寫一個吧。
字元串比對嘛，無非就是兩個指針，分别指向主串和模式串，然後依次往後移，檢查是否一緻。在遇到不能比對的情況時（簡稱“失配”），一般的方法，就是讓兩個指針回溯，主串指針往後再移動一位，從頭開始比對。這其中做了很多重複勞動，我們可以分析一下：
可以看到模式串在比對到下标5時失配了。
我們抓出模式串和主串在前方比對的5個字元，并在模式串部分的前端和主串部分的後端找到了一對最長的相等的字串（不等于原來的串），用陰影标記一下，後面有用。
接着移動模式串，繼續比對：
看出什麼規律了麼？每次比較，其實都是“abaab”的前端和後端的字串進行比較：
第一回是"abaa"vs"baab"
第二回是"aba"vs"aab"
第三回是"ab"vs"ab"
可見，隻有在模式串部分的前端和主串部分的後端重合的時候，才可能繼續比對。
是這樣麼？當然是的，因為我們之前找出的是最長的，相等的字串！
這樣就能把中間無效的對比步驟省略，主串的指針不變，模式串的指針直接跳到下标2繼續比對。這裡的下标2就等于最長相等字串的長度。
接着推廣到更一般的情形：
假設主串s，模式串patten，s和patten分别在下标i，j處失配，
如果j>0，那麼，
顯而易見，'si-k...si-1' = 'patten0...pattenk-1'，此串長度為k，故下一步模式串指針應當跳轉到下标k繼續比對。
在這裡，因為'si-k...si-1' = 'pattenj-k...pattenj-1'，得到'patten0...pattenk-1' = 'pattenj-k...pattenj-1'，是以給定patten和j的情況下，k的值也是固定的。
如果j=0，那麼i應當往後挪一位，j不變，重頭比對
至此，對于給定的patten，可以得到一個j->k的映射關系，記為數組next，其中，k = next[j]：
next[j] = Max{ k | 0<=k<j 并且 'patten0...pattenk-1' = 'pattenj-k...pattenj-1' }
當且僅當j == 0時，next[j] = -1（-1其實是沒有意義的，在這裡為了計算友善）
依照這個定義，已經可以寫出一個計算next的弱弱的實作了。不過我先買個關子，先把主串的比對搞定再說。
有了之前的分析，主串比對的代碼基本就可以一蹴而就了（Java代碼）：
這兒有一處很巧妙地的地方：
next[0]是恒為-1的，是以如果在下标0處失配，則下一次循環j等于-1，i就會在循環中指向下一個字元，j也恢複為0。
看下面這張圖
假設模式串上的下标i，模式串下的下标j，那麼
顯然next[5] = 2是由patteni=4 = pattenj=1推出的，
推廣到一般的情況，也就是說當patten與自身錯位比對時，當他們在i，j（i>j）處比對時，
此時可以得到next[i+1] = j+1
如果j = 0時就失配了的話，自然next[i+1]應當等于0
至此，寫出代碼也就不難了，有些小技巧卻要注意一下（Java代碼）：
這個求next數組的方式和KMP算法的主體是不是很像呢？