知識星球
沒碰演演算法久了大腦生鏽得好快，看著 KMP 居然大腦一片空白，死活想不出當初怎麼求 next 陣列。google 一下，急躁地參考了一堆部落格後終於想起來了。為了避免以後忘了又要浪費時間搜一遍，不如自己總結一篇吧！希望我的表述能幫更多人理解這個巧(qi)妙(pa)的演演算法。
KMP 演演算法是什麼？
- KMP 代表三個作者的名字，看維基去吧。
- 這是一個字串查詢演演算法，可以在一個字串（S）中查詢一個詞（W）出現的位置。
KMP 演演算法怎麼查詢？
說起字串查詢，大家肯定能理解樸素的查法，就是以 S 每個字元為開頭與 W 比較。O(m*n)
這時，一群熱(xian)愛(de)思(dan)考(teng)的人就想，我覺得不夠快，能不能再最佳化成 O(m+n) 啊？別說還真可以。
看下圖，現在字串查詢過程中出現了不匹配：
按樸素演演算法，這裡 W 應該右移一位然後重新匹配。但是，你有沒有發現，目前為止，綠色部分在兩個字串中都是已知的。於是就有人想，如果出現下圖這樣的情況就好了：
如果是這樣的話，我們就不用一個個比較了，直接滑動，跳過不匹配的就好：
以上就是 KMP 演演算法的思想啦，就是找到最長的滑動區間，是不是很簡單！
怎麼確定滑動區間？
我們可以建立一個陣列，叫 next ，它跟 W 串一樣長，next[ j ] 表示當 W[ j ] 與 S[ i ] 不匹配時，W 應該滑到哪個位置上。
所以一但不匹配時，查一下 next 值，讓 S[ i ] 跟 W[next[ j ]] 繼續比較就行啦。
現在的問題就變為：怎麼計算 next 陣列？
先看回上面的圖二，要求 next 陣列必須先知道藍色部分才行。這就頭大了，我們是要先求 next 陣列再做匹配啊，那求 next 的時候肯定不能碰 S 串，不然就相當於沒優化了。
但是不看 S 串又怎麼知道藍色部分相等了！你坑爹啊！
有沒有開始煩了……稍安勿躁！（我最近剛嘗試了畫一了一幅 Low Poly，結果現在眼睛那個累啊！打心底佩服設計師們！）
再看回上面圖二，由於綠色部分都是已經匹配的！所以就有了下麵的關係：
之前我們假設了 2 和 3 是匹配的，現在看出了什麼蹊蹺沒有？有沒有豁然開朗的感覺？
沒錯，既然 2 與 3 是匹配的，2 與 4 是匹配的，那麼 3 與 4 是不是一定是匹配的！有了這個傳遞關係我們現在只用 W 串就可以求出 next 陣列啦！是不是省了很多時間！
準備求 next 陣列
這節是求 next 陣列前的一些熱身概念，如果你有信心，可以直接跳到下一節。
1、對於 next[ 1 ]，請看灰色部分，在第二組中，因為 W[ 1 ]（圖中的 a）前面只有一個字元（b），所以只要 W[ 1 ] 不匹配，不管 W[ 0 ] 是不是藍色，W 總是會滑到開頭的（圖第三組）。好好理解這句話。
所以 next[ 1 ] == 0 總是成立的，這是一種特殊情況。你可以順著灰色條看上去（註意是灰色部分哦），圖第二組中 c 對應 W 的位置 1 在第三組是不是變成對應 0 了。
2、對於 next[ 0 ]，繼續看圖灰色部分，在第三組中，W[ 0 ]（b）就與 c 不匹配了，且 W[ 0 ] 左邊已經沒有字元了，這表示 S[ i ]（圖中 c）肯定沒戲了，所以要將 W 滑到 c 下一個字元的位置重新開始（圖第四組），灰色部分的 0 現在是不是變成 -1 了。所以 next[ 0 ] = -1。這也是一種特殊情況。
3、最後再講一下求 next 的核心思想，看下圖中間的 W 。跟前面一樣藍色部分代表相等，於是有 W[ i ] == W[ j ]（j < i）。可以想象如果在 W 和 S 匹配過程中 W[ i+1 ] 不匹配了（與上面 S 的紅色部分），那麼 W 就要滑動且 W[ j+1 ] 將改寫在 W[ i+1 ] 上（看最下麵的 W）。所以 W[ i ] == W[ j ] 可以得出 next[ i+1 ] = j+1。
求解 next 陣列
說了這麼多，終於可以開始求解 next 陣列啦！
先看下圖：
假設求 next 陣列過程到達了上面的階段，即剛利用 i-1 求完 next[ i ]，現在利用 i 求 next[ i+1 ]。我們可以知道藍色部分是相等的，因為剛剛求完 next[ i ] = j。現在對於 W[ i ] 和 W[ j ] 有兩種情況：
- W[ i ] 和 W[ j ] 相等。這好辦，參照上一節第 3 點，next[ i+1 ] = j + 1，然後 W[ i ] 和 W[ j ] 都向前繼續看下一個字元（i += 1、j += 1）。（相當於把 W[ i ] 和 W[ j ] 合併到各自的藍色部分中去）。
- W[ i ] 和 W[ j ] 不等。這時就要試圖找下圖的關係咯：試圖在 j 裡找到一個 k，滿足 W[ k ] == W[ i ] 且綠色部分相等。（雖然比 j 短一點，但有總比沒有爽嘛。）
怎麼確定 k 的位置？再仔細看一下上圖，前面用過的一個策略，現在又要用上咯：
因為 1 和 2 相等，2 和 3 相等，所以 1 和 3 相等。所以現在變成了跟前面一模一樣的問題 —— 只是規模變小了。嗅出動態規劃的味道沒有？假設你不知道動態規劃，我們繼續分析。
有了上面的傳遞關係，我們可以知道 k = next[ j ]，可以理解不？把上圖左邊一半單獨看，假設在 W 和 S 匹配過程中 W[ j ] 不匹配了，那肯定是要滑到 next[ j ] 對不對？按照 next 陣列的含義我們知道 next[ j ] 表示綠色部分是最長的咯，我們正好要為 k 找這樣的值，所以 k = next[ j ]。
但如果 W[ k ] 和 W[ i ] 也是不相等呢？沒關係，對 k 進行同樣的查詢（k = next[ k ]），再看有沒有短一點的……一直找直到 -1 。
再次總結一下剛才的兩種情況，對於 W[ i ] 和 W[ j ]：
- W[ i ] 和 W[ j ] 相等。next[ i+1 ] = j + 1，i += 1，j += 1。
- W[ i ] 和 W[ j ] 不等。j = next[ j ]。再次重覆進行比較。
程式碼片段：
if (w.charAt(i) === w.charAt(j)) {
// 匹配成功之後兩者都跳到下一字元繼續匹配
next[++i] = ++j;
} else {
// 滑動 j 繼續匹配（短了一點還是可以接受嘛）
j = next[ j ];
}
再看一下邊界的問題，從前面一節的圖可以知道，滑動最多滑到 -1，代表最左側的空位咯，所以 j 滑動的最壞情況是滑到了 -1 。從前面一節我們也知道 j == -1 時, next[ i+1 ] == 0 == j + 1，所以：
if (j === -1 || w.charAt(i) === w.charAt(j)) {
next[++i] = ++j;
} else {
j = next[ j ];
}
現在考慮迴圈的問題，求 next 陣列只需利用 i 遍歷一遍。而對於 j ，因為 next[ 0 ] == -1，所以 j 初值為 -1 。再回想前面一節的第三點，我們是以 i 位置去算 next[ i+1 ] 的，所以 i 在 W1（即 W）倒數第二個位置就可以停止了。
var next = []
, i = 0
, j = -1
;
while (i < w.length-1) {
if (j === -1 || w.charAt(i) === w.charAt(j)) {
next[++i] = ++j;
} else {
j = next[j];
}
}
就這樣求完 next 陣列啦！是不是超簡單啊！
這裡看不懂的話可以繼續討論。
小最佳化
對於 aaaab 這類的串，按上面的求法得出的 next 陣列是 [-1,0,1,2,3]。其實對於中間的幾個 a 來說，當其不匹配的時候，滑動到前面一位的 a 肯定也是不匹配了。所以應該直接滑到最前的一個 a 那裡 [-1,-1,-1,-1,3]。
怎麼實現呢？自己想吧！
弱弱的還是寫一下吧，免得被人噴。
因為是以 i 求 next[ i+1 ]，那麼只需判斷一下 W[ i ] 是否等於 W[ i+1 ] 不就得了。
while (i < w.length-1) {
if (j === -1 || w.charAt(i) === w.charAt(j)) {
if (w.charAt(++i) !== w.charAt(++j)) {
next[i] = j;
} else {
next[i] = next[j];
}
} else {
j = next[j];
}
}
KMP 演演算法實現
得到了 next 陣列後就開始實現 KMP 匹配演演算法咯。其實跟求 next 陣列大同小異。按照前面講過的思路實現就行。最後如果 j 達到了 W 的長度，說明 W 字元全部匹配成功了。
i = j = 0;
while (i < s.length && j < w.length) {
if (j === -1 || s.charAt(i) === w.charAt(j)) {
i += 1;
j += 1;
} else {
j = next[j];
}
}
if (j >= w.length) {
return (i – w.length);
} else {
return 0;
}
以上就是 KMP 演演算法啦，希望你以後都能記起來，寫完這篇我是忘不了的啦。
有什麼問題可以評論，本文的完整原始碼（JavaScript）以及圖片的 PSD 源檔案都在[這裡]，有需要的可以 star。就這樣，麼麼扎~
參考資料
- 字串匹配的KMP演演算法 – 阮一峰
- The Knuth Morris Pratt Algorithm In My Own Words – Jake Boxer
- Knuth–Morris–Pratt Algorithm – Wikipedia
原文出處： 伯樂線上 – Jaward華仔