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