KMP 算法（Knuth-Morris-Pratt 算法）是一個著名的字符串匹配算法，效率很高，但是確實有點複雜。
很多讀者抱怨 KMP 算法無法理解，這很正常，想到大學教材上關於 KMP 算法的講解，也不知道有多少未來的 Knuth、Morris、Pratt 被提前勸退了。有一些優秀的同學通過手推 KMP 算法的過程來輔助理解該算法，這是一種辦法，不過本文要從邏輯層面幫助讀者理解算法的原理。十行代碼之間，KMP 灰飛煙滅。
先在開頭約定，本文用pat表示模式串，長度為M，txt表示文本串，長度為N。KMP 算法是在txt中查找子串pat，如果存在，返回這個子串的起始索引，否則返回 -1。
為什麼我認為 KMP 算法就是個動態規劃問題呢，等會有解釋。對於動態規劃，之前多次強調了要明確dp數組的含義，而且同一個問題可能有不止一種定義dp數組含義的方法，不同的定義會有不同的解法。
讀者見過的 KMP 算法應該是，一波詭異的操作處理pat後形成一個一維的數組next，然後根據這個數組經過又一波複雜操作去匹配txt。時間複雜度 O(N)，空間複雜度 O(M)。其實它這個next數組就相當於dp數組，其中元素的含義跟pat的前綴和後綴有關，判定規則比較複雜，不太好理解。
本文則用一個二維的dp數組（但空間複雜度還是 O(M)），重新定義其中元素的含義，使得代碼長度大大減少，可解釋性大大提高。
PS：本文的代碼參考《算法4》，原代碼使用的數組名稱是dfa（確定有限狀態機），因為我們的公眾號之前有一系列動態規劃的文章，就不說這麼高大上的名詞了，本文還是沿用dp數組的名稱。
一、KMP 算法概述首先還是簡單介紹一下 KMP 算法和暴力匹配算法的不同在哪裡，難點在哪裡，和動態規劃有啥關係。
暴力的字符串匹配算法很容易寫，看一下它的運行邏輯：
int search(String pat, String txt) {
int M = pat.length;
int N = txt.length;
for (int i = 0; i < N - M; i++) {
int j;
for (j = 0; j < M; j++) {
if (pat[j] != txt[i+j])
break;
}
if (j == M) return i;
}
return -1;
}
對於暴力算法，如果出現不匹配字符，同時回退txt和pat的指針，嵌套 for 循環，時間複雜度 O(MN)，空間複雜度O(1)。最主要的問題是，如果字符串中重複的字符比較多，該算法就顯得很蠢。
比如 txt = "aaacaaab" pat = "aaab"：
暴力算法很明顯，pat中根本沒有字符 c，根本沒必要回退指針i，暴力解法明顯多做了很多不必要的操作。
KMP 算法的不同之處在於，它會花費空間來記錄一些信息，在上述情況中就會顯得很聰明：
kmp算法再比如類似的 txt = "aaaaaaab" pat = "aaab"，暴力解法還會和上面那個例子一樣蠢蠢地回退指針i，而 KMP 算法又會耍聰明：
kmp算法因為 KMP 算法知道字符 b 之前的字符 a 都是匹配的，所以每次只需要比較字符 b 是否被匹配就行了。
KMP 算法永不回退txt的指針i，不走回頭路（不會重複掃描txt），而是藉助dp數組中儲存的信息把pat移到正確的位置繼續匹配，時間複雜度只需 O(N)，用空間換時間，所以我認為它是一種動態規划算法。
KMP 算法的難點在於，如何計算dp數組中的信息？如何根據這些信息正確地移動pat的指針？這個就需要確定有限狀態自動機來輔助了，別怕這種高大上的文學詞彙，其實和動態規劃的dp數組如出一轍，等你學會了也可以拿這個詞去嚇唬別人。
還有一點需要明確的是：計算這個dp數組，只和pat串有關。意思是說，只要給我個pat，我就能通過這個模式串計算出dp數組，然後你可以給我不同的txt，我都不怕，利用這個dp數組我都能在 O(N) 時間完成字符串匹配。
具體來說，比如上文舉的兩個例子：
txt1 = "aaacaaab"
pat = "aaab"
txt2 = "aaaaaaab"
pat = "aaab"
我們的txt不同，但是pat是一樣的，所以 KMP 算法使用的dp數組是同一個。
只不過對於txt1的下面這個即將出現的未匹配情況：
dp數組指示pat這樣移動：
PS：這個j不要理解為索引，它的含義更準確地說應該是狀態（state），所以它會出現這個奇怪的位置，後文會詳述。
而對於txt2的下面這個即將出現的未匹配情況：
dp數組指示pat這樣移動：
明白了dp數組只和pat有關，那麼我們這樣設計 KMP 算法就會比較漂亮：
public class KMP {
private int[][] dp;
private String pat;
public KMP(String pat) {
this.pat = pat;
}
public int search(String txt) {
}
}
這樣，當我們需要用同一pat去匹配不同txt時，就不需要浪費時間構造dp數組了：
KMP kmp = new KMP("aaab");
int pos1 = kmp.search("aaacaaab");
int pos2 = kmp.search("aaaaaaab");
為什麼說 KMP 算法和狀態機有關呢？是這樣的，我們可以認為pat的匹配就是狀態的轉移。比如當 pat = "ABABC"：
如上圖，圓圈內的數字就是狀態，狀態 0 是起始狀態，狀態 5（pat.length）是終止狀態。開始匹配時pat處於起始狀態，一旦轉移到終止狀態，就說明在txt中找到了pat。
比如說如果當前處於狀態 2，就說明字符 "AB" 被匹配：
另外，處於某個狀態時，遇到不同的字符，pat狀態轉移的行為也不同。比如說假設現在匹配到了狀態 4，如果遇到字符 A 就應該轉移到狀態 3，遇到字符 C 就應該轉移到狀態 5，如果遇到字符 B 就應該轉移到狀態 0：
具體什麼意思呢，舉例解釋一下。用變量j表示指向當前狀態的指針，當前pat匹配到了狀態 4：
如果遇到了字符 "A"，根據箭頭指示，轉移到狀態 3 是最聰明的：
如果遇到了字符 "B"，根據箭頭指示，只能轉移到狀態 0（一夜回到解放前）：
如果遇到了字符 "C"，根據箭頭指示，應該轉移到終止狀態 5，這也就意味著匹配完成：
當然了，還可能遇到其他字符，比如 Z，但是顯然應該轉移到起始狀態 0，因為pat中根本都沒有字符 Z：
這裡為了清晰起見，我們畫狀態圖時就把其他字符轉移到狀態 0 的箭頭省略，只畫pat中出現的字符的狀態轉移：
KMP 算法最關鍵的步驟就是構造這個狀態轉移圖。要確定狀態轉移的行為，得明確兩個變量，一個是當前的匹配狀態，另一個是遇到的字符；確定了這兩個變量後，就可以知道這個情況下應該轉移到哪個狀態。
下面看一下 KMP 算法根據這幅狀態轉移圖匹配字符串txt的過程：
kmp算法運行過程
請記住這個 GIF 的匹配過程，這就是 KMP 算法的核心邏輯！
為了描述狀態轉移圖，我們定義一個二維 dp 數組，它的含義如下：
dp[j][c] = next
0 <= j < M，代表當前的狀態
0 <= c < 256，代表遇到的字符（ASCII 碼）
0 <= next <= M，代表下一個狀態
dp[4]['A'] = 3 表示：
當前是狀態 4，如果遇到字符 A，
pat 應該轉移到狀態 3
dp[1]['B'] = 2 表示：
當前是狀態 1，如果遇到字符 B，
pat 應該轉移到狀態 2
根據我們這個 dp 數組的定義和剛才狀態轉移的過程，我們可以先寫出 KMP 算法的 search 函數代碼：
public int search(String txt) {
int M = pat.length();
int N = txt.length();
int j = 0;
for (int i = 0; i < N; i++) {
j = dp[j][txt.charAt(i)];
if (j == M) return i - M + 1;
}
return -1;
}
到這裡，應該還是很好理解的吧，dp數組就是我們剛才畫的那幅狀態轉移圖，如果不清楚的話回去看下 GIF 的算法演進過程。
下面講解：如何通過pat構建這個dp數組？
三、構建狀態轉移圖回想剛才說的：要確定狀態轉移的行為，必須明確兩個變量，一個是當前的匹配狀態，另一個是遇到的字符，而且我們已經根據這個邏輯確定了dp數組的含義，那麼構造dp數組的框架就是這樣：
for 0 <= j < M:
for 0 <= c < 256:
dp[j][c] = next
這個 next 狀態應該怎麼求呢？顯然，如果遇到的字符c和pat[j]匹配的話，狀態就應該向前推進一個，也就是說next = j + 1，我們不妨稱這種情況為狀態推進：
如果遇到的字符c和pat[j]不匹配的話，狀態就要回退（或者原地不動），我們不妨稱這種情況為狀態重啟：
那麼，如何得知在哪個狀態重啟呢？解答這個問題之前，我們再定義一個名字：影子狀態（我編的名字），用變量X表示。所謂影子狀態，就是和當前狀態具有相同的前綴。比如下面這種情況：
當前狀態j = 4，其影子狀態為X = 2，它們都有相同的前綴 "AB"。因為狀態X和狀態j存在相同的前綴，所以當狀態j準備進行狀態重啟的時候（遇到的字符c和pat[j]不匹配），可以通過X的狀態轉移圖來獲得最近的重啟位置。
比如說剛才的情況，如果狀態j遇到一個字符 "A"，應該轉移到哪裡呢？首先狀態 4 只有遇到 "C" 才能推進狀態，遇到 "A" 顯然只能進行狀態重啟。狀態j會把這個字符委託給狀態X處理，也就是dp[j]['A'] = dp[X]['A']：
為什麼這樣可以呢？因為：既然j這邊已經確定字符 "A" 無法推進狀態，只能回退，而且 KMP 算法就是要儘可能少的回退，以免多餘的計算。那麼j就可以去問問和自己具有相同前綴的X，如果X遇見 "A" 可以進行「狀態推進」，那就轉移過去，因為這樣回退最少：
當然，如果遇到的字符是 "B"，狀態X也不能進行「狀態推進」，只能回退，j只要跟著X指引的方向回退就行了：
你也許會問，這個X怎麼知道遇到字符 "B" 要回退到狀態 0 呢？因為X永遠跟在j的身後，狀態X如何轉移，在之前就已經算出來了。動態規划算法不就是利用過去的結果解決現在的問題嗎？
PS：對這裡不理解的同學建議讀讀這篇舊文 動態規劃設計之最長遞增子序列。
這樣，我們就可以細化一下剛才的框架代碼：
int X
for 0 <= j < M:
for 0 <= c < 256:
if c == pat[j]:
dp[j][c] = j + 1
else:
dp[j][c] = dp[X][c]
如果之前的內容你都能理解，恭喜你，現在就剩下一個問題：影子狀態X是如何得到的呢？下面先直接看完整代碼吧。
public class KMP {
private int[][] dp;
private String pat;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
dp = new int[M][256];
dp[0][pat.charAt(0)] = 1;
int X = 0;
for (int j = 1; j < M; j++) {
for (int c = 0; c < 256; c++) {
if (pat.charAt(j) == c)
dp[j][c] = j + 1;
else
dp[j][c] = dp[X][c];
}
X = dp[X][pat.charAt(j)];
}
}
public int search(String txt) {...}
}
先解釋一下這一行代碼：
dp[0][pat.charAt(0)] = 1;
這行代碼是 base case，只有遇到 pat[0] 這個字符才能使狀態從 0 轉移到 1，遇到其它字符的話還是停留在狀態 0（Java 默認初始化數組全為 0）。
影子狀態X是先初始化為 0，然後隨著j的前進而不斷更新的。下面看看到底應該如何更新影子狀態X：
int X = 0;
for (int j = 1; j < M; j++) {
...
X = dp[X][pat.charAt(j)];
}
更新X其實和search函數中更新狀態j的過程是非常相似的：
int j = 0;
for (int i = 0; i < N; i++) {
j = dp[j][txt.charAt(i)];
...
}
其中的原理非常微妙，注意代碼中 for 循環的變量初始值，可以這樣理解：後者是在txt中匹配pat，前者是在pat中匹配pat[1:]，狀態X總是落後狀態j一個狀態，與j具有最長的相同前綴。所以我把X比喻為影子狀態，似乎也有一點貼切。
另外，構建 dp 數組是根據 base casedp[0][..]向後推演。這就是我認為 KMP 算法就是一種動態規划算法的原因。
下面來看一下狀態轉移圖的完整構造過程，你就能理解狀態X作用之精妙了：
狀態轉移構造過程
至此，KMP 算法就已經再無奧妙可言了！看下 KMP 算法的完整代碼吧：