讀完本文应闯，你可以去力扣拿下如下題目：
-----------
KMP 算法（Knuth-Morris-Pratt 算法）是一個著名的字符串匹配算法坛梁，效率很高愕把，但是確實(shí)有點(diǎn)復(fù)雜粘室。
很多讀者抱怨 KMP 算法無法理解栓辜，這很正常，想到大學(xué)教材上關(guān)于 KMP 算法的講解隧土，也不知道有多少未來的 Knuth提针、Morris、Pratt 被提前勸退了次洼。有一些優(yōu)秀的同學(xué)通過手推 KMP 算法的過程來輔助理解該算法关贵，這是一種辦法，不過本文要從邏輯層面幫助讀者理解算法的原理卖毁。十行代碼之間揖曾，KMP 灰飛煙滅。
先在開頭約定亥啦，本文用 pat 表示模式串炭剪，長度為 M，txt 表示文本串翔脱，長度為 N奴拦。KMP 算法是在 txt 中查找子串 pat，如果存在届吁，返回這個子串的起始索引错妖，否則返回 -1绿鸣。
為什么我認(rèn)為 KMP 算法就是個動態(tài)規(guī)劃問題呢，等會再解釋暂氯。對于動態(tài)規(guī)劃潮模，之前多次強(qiáng)調(diào)了要明確 dp 數(shù)組的含義，而且同一個問題可能有不止一種定義 dp 數(shù)組含義的方法痴施，不同的定義會有不同的解法擎厢。
讀者見過的 KMP 算法應(yīng)該是，一波詭異的操作處理 pat 后形成一個一維的數(shù)組 next辣吃，然后根據(jù)這個數(shù)組經(jīng)過又一波復(fù)雜操作去匹配 txt动遭。時間復(fù)雜度 O(N)，空間復(fù)雜度 O(M)神得。其實(shí)它這個 next 數(shù)組就相當(dāng)于 dp 數(shù)組厘惦，其中元素的含義跟 pat 的前綴和后綴有關(guān)，判定規(guī)則比較復(fù)雜循头，不好理解绵估。本文則用一個二維的 dp 數(shù)組（但空間復(fù)雜度還是 O(M)），重新定義其中元素的含義卡骂，使得代碼長度大大減少国裳，可解釋性大大提高。
PS：本文的代碼參考《算法4》全跨，原代碼使用的數(shù)組名稱是 dfa（確定有限狀態(tài)機(jī)）缝左，因?yàn)槲覀兊墓娞栔坝幸幌盗袆討B(tài)規(guī)劃的文章，就不說這么高大上的名詞了浓若，我對書中代碼進(jìn)行了一點(diǎn)修改渺杉，并沿用 dp 數(shù)組的名稱。
一挪钓、KMP 算法概述
首先還是簡單介紹一下 KMP 算法和暴力匹配算法的不同在哪里是越，難點(diǎn)在哪里，和動態(tài)規(guī)劃有啥關(guān)系碌上。
暴力的字符串匹配算法很容易寫倚评，看一下它的運(yùn)行邏輯：
// 暴力匹配（偽碼）
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)，時間復(fù)雜度 O(MN)霞丧，空間復(fù)雜度O(1)呢岗。最主要的問題是，如果字符串中重復(fù)的字符比較多，該算法就顯得很蠢后豫。
比如 txt = "aaacaaab" pat = "aaab"：
很明顯悉尾，pat 中根本沒有字符 c，根本沒必要回退指針 i挫酿，暴力解法明顯多做了很多不必要的操作焕襟。
KMP 算法的不同之處在于，它會花費(fèi)空間來記錄一些信息饭豹，在上述情況中就會顯得很聰明：
再比如類似的 txt = "aaaaaaab" pat = "aaab"，暴力解法還會和上面那個例子一樣蠢蠢地回退指針 i务漩，而 KMP 算法又會耍聰明：
因?yàn)?KMP 算法知道字符 b 之前的字符 a 都是匹配的拄衰，所以每次只需要比較字符 b 是否被匹配就行了。
KMP 算法永不回退 txt 的指針 i饵骨，不走回頭路（不會重復(fù)掃描 txt）翘悉，而是借助 dp 數(shù)組中儲存的信息把 pat 移到正確的位置繼續(xù)匹配，時間復(fù)雜度只需 O(N)居触，用空間換時間妖混，所以我認(rèn)為它是一種動態(tài)規(guī)劃算法。
KMP 算法的難點(diǎn)在于轮洋，如何計算 dp 數(shù)組中的信息制市？如何根據(jù)這些信息正確地移動 pat 的指針？這個就需要確定有限狀態(tài)自動機(jī)來輔助了弊予，別怕這種高大上的文學(xué)詞匯祥楣，其實(shí)和動態(tài)規(guī)劃的 dp 數(shù)組如出一轍，等你學(xué)會了也可以拿這個詞去嚇唬別人汉柒。
還有一點(diǎn)需要明確的是：計算這個 dp 數(shù)組误褪，只和 pat 串有關(guān)。意思是說碾褂，只要給我個 pat兽间，我就能通過這個模式串計算出 dp 數(shù)組，然后你可以給我不同的 txt正塌，我都不怕嘀略，利用這個 dp 數(shù)組我都能在 O(N) 時間完成字符串匹配。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)传货，手把手刷 200 道力扣題目税产，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新炼蹦。建議收藏颓遏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了粮宛。
具體來說窥淆，比如上文舉的兩個例子：
txt1 = "aaacaaab"
pat = "aaab"
txt2 = "aaaaaaab"
pat = "aaab"
我們的 txt 不同卖宠，但是 pat 是一樣的，所以 KMP 算法使用的 dp 數(shù)組是同一個忧饭。
只不過對于 txt1 的下面這個即將出現(xiàn)的未匹配情況：
dp 數(shù)組指示 pat 這樣移動：
PS：這個j 不要理解為索引扛伍，它的含義更準(zhǔn)確地說應(yīng)該是狀態(tài)（state），所以它會出現(xiàn)這個奇怪的位置词裤，后文會詳述刺洒。
而對于 txt2 的下面這個即將出現(xiàn)的未匹配情況：
dp 數(shù)組指示 pat 這樣移動：
明白了 dp 數(shù)組只和 pat 有關(guān)，那么我們這樣設(shè)計 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) 時間
}
}
這樣吼砂，當(dāng)我們需要用同一 pat 去匹配不同 txt 時逆航，就不需要浪費(fèi)時間構(gòu)造 dp 數(shù)組了：
KMP kmp = new KMP("aaab");
int pos1 = kmp.search("aaacaaab"); //4
int pos2 = kmp.search("aaaaaaab"); //4
二、狀態(tài)機(jī)概述
為什么說 KMP 算法和狀態(tài)機(jī)有關(guān)呢渔肩？是這樣的因俐，我們可以認(rèn)為 pat 的匹配就是狀態(tài)的轉(zhuǎn)移。比如當(dāng) pat = "ABABC"：
如上圖周偎，圓圈內(nèi)的數(shù)字就是狀態(tài)抹剩，狀態(tài) 0 是起始狀態(tài)，狀態(tài) 5（pat.length）是終止?fàn)顟B(tài)蓉坎。開始匹配時 pat 處于起始狀態(tài)澳眷，一旦轉(zhuǎn)移到終止?fàn)顟B(tài)，就說明在 txt 中找到了 pat蛉艾。比如說當(dāng)前處于狀態(tài) 2境蔼，就說明字符 "AB" 被匹配：
另外，處于不同狀態(tài)時伺通，pat 狀態(tài)轉(zhuǎn)移的行為也不同箍土。比如說假設(shè)現(xiàn)在匹配到了狀態(tài) 4，如果遇到字符 A 就應(yīng)該轉(zhuǎn)移到狀態(tài) 3罐监，遇到字符 C 就應(yīng)該轉(zhuǎn)移到狀態(tài) 5吴藻，如果遇到字符 B 就應(yīng)該轉(zhuǎn)移到狀態(tài) 0：
具體什么意思呢，我們來一個個舉例看看弓柱。用變量 j 表示指向當(dāng)前狀態(tài)的指針沟堡，當(dāng)前 pat 匹配到了狀態(tài) 4：
如果遇到了字符 "A"，根據(jù)箭頭指示矢空，轉(zhuǎn)移到狀態(tài) 3 是最聰明的：
如果遇到了字符 "B"航罗，根據(jù)箭頭指示，只能轉(zhuǎn)移到狀態(tài) 0（一夜回到解放前）：
如果遇到了字符 "C"屁药，根據(jù)箭頭指示粥血，應(yīng)該轉(zhuǎn)移到終止?fàn)顟B(tài) 5，這也就意味著匹配完成：
當(dāng)然了，還可能遇到其他字符复亏，比如 Z趾娃，但是顯然應(yīng)該轉(zhuǎn)移到起始狀態(tài) 0，因?yàn)?pat 中根本都沒有字符 Z：
這里為了清晰起見缔御，我們畫狀態(tài)圖時就把其他字符轉(zhuǎn)移到狀態(tài) 0 的箭頭省略抬闷，只畫 pat 中出現(xiàn)的字符的狀態(tài)轉(zhuǎn)移：
KMP 算法最關(guān)鍵的步驟就是構(gòu)造這個狀態(tài)轉(zhuǎn)移圖。要確定狀態(tài)轉(zhuǎn)移的行為耕突，得明確兩個變量笤成，一個是當(dāng)前的匹配狀態(tài)，另一個是遇到的字符眷茁；確定了這兩個變量后疹启，就可以知道這個情況下應(yīng)該轉(zhuǎn)移到哪個狀態(tài)。
下面看一下 KMP 算法根據(jù)這幅狀態(tài)轉(zhuǎn)移圖匹配字符串 txt 的過程：
請記住這個 GIF 的匹配過程蔼卡，這就是 KMP 算法的核心邏輯！
為了描述狀態(tài)轉(zhuǎn)移圖挣磨，我們定義一個二維 dp 數(shù)組雇逞，它的含義如下：
dp[j][c] = next
0 <= j < M，代表當(dāng)前的狀態(tài)
0 <= c < 256茁裙，代表遇到的字符（ASCII 碼）
0 <= next <= M塘砸，代表下一個狀態(tài)
dp[4]['A'] = 3 表示：
當(dāng)前是狀態(tài) 4，如果遇到字符 A晤锥，
pat 應(yīng)該轉(zhuǎn)移到狀態(tài) 3
dp[1]['B'] = 2 表示：
當(dāng)前是狀態(tài) 1掉蔬，如果遇到字符 B，
pat 應(yīng)該轉(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++) {
// 當(dāng)前是狀態(tài) j女轿，遇到字符 txt[i]，
// pat 應(yīng)該轉(zhuǎn)移到哪個狀態(tài)壕翩？
j = dp[j][txt.charAt(i)];
// 如果達(dá)到終止態(tài)蛉迹，返回匹配開頭的索引
if (j == M) return i - M + 1;
}
// 沒到達(dá)終止態(tài)，匹配失敗
return -1;
}
到這里放妈，應(yīng)該還是很好理解的吧北救，dp 數(shù)組就是我們剛才畫的那幅狀態(tài)轉(zhuǎn)移圖，如果不清楚的話回去看下 GIF 的算法演進(jìn)過程芜抒。下面講解：如何通過 pat 構(gòu)建這個 dp 數(shù)組珍策？
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目宅倒，全部發(fā)布在 labuladong的算法小抄攘宙，持續(xù)更新。建議收藏，按照我的文章順序刷題模聋，掌握各種算法套路后投再入題海就如魚得水了肩民。
三、構(gòu)建狀態(tài)轉(zhuǎn)移圖
回想剛才說的：要確定狀態(tài)轉(zhuǎn)移的行為链方，必須明確兩個變量持痰，一個是當(dāng)前的匹配狀態(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)應(yīng)該怎么求呢？顯然前酿，如果遇到的字符 c 和 pat[j] 匹配的話患雏，狀態(tài)就應(yīng)該向前推進(jìn)一個，也就是說 next = j + 1罢维，我們不妨稱這種情況為狀態(tài)推進(jìn)：
如果字符 c 和 pat[j] 不匹配的話淹仑，狀態(tài)就要回退（或者原地不動），我們不妨稱這種情況為狀態(tài)重啟：
那么肺孵，如何得知在哪個狀態(tài)重啟呢匀借？解答這個問題之前，我們再定義一個名字：影子狀態(tài)（我編的名字）平窘，用變量 X 表示吓肋。所謂影子狀態(tài)，就是和當(dāng)前狀態(tài)具有相同的前綴瑰艘。比如下面這種情況：
當(dāng)前狀態(tài) j = 4是鬼，其影子狀態(tài)為 X = 2，它們都有相同的前綴 "AB"紫新。因?yàn)闋顟B(tài) X 和狀態(tài) j 存在相同的前綴均蜜，所以當(dāng)狀態(tài) j 準(zhǔn)備進(jìn)行狀態(tài)重啟的時候（遇到的字符 c 和 pat[j] 不匹配），可以通過 X 的狀態(tài)轉(zhuǎn)移圖來獲得最近的重啟位置芒率。
比如說剛才的情況兆龙，如果狀態(tài) j 遇到一個字符 "A"，應(yīng)該轉(zhuǎn)移到哪里呢敲董？首先只有遇到 "C" 才能推進(jìn)狀態(tài)紫皇，遇到 "A" 顯然只能進(jìn)行狀態(tài)重啟。狀態(tài) j 會把這個字符委托給狀態(tài) X 處理腋寨，也就是 dp[j]['A'] = dp[X]['A']：
為什么這樣可以呢聪铺？因?yàn)椋杭热?j 這邊已經(jīng)確定字符 "A" 無法推進(jìn)狀態(tài)，只能回退萄窜，而且 KMP 就是要盡可能少的回退铃剔，以免多余的計算撒桨。那么 j 就可以去問問和自己具有相同前綴的 X，如果 X 遇見 "A" 可以進(jìn)行「狀態(tài)推進(jìn)」键兜，那就轉(zhuǎn)移過去凤类，因?yàn)檫@樣回退最少。
當(dāng)然普气，如果遇到的字符是 "B"谜疤，狀態(tài) X 也不能進(jìn)行「狀態(tài)推進(jìn)」，只能回退现诀，j 只要跟著 X 指引的方向回退就行了：
你也許會問夷磕，這個 X 怎么知道遇到字符 "B" 要回退到狀態(tài) 0 呢？因?yàn)?X 永遠(yuǎn)跟在 j 的身后仔沿，狀態(tài) X 如何轉(zhuǎn)移坐桩，在之前就已經(jīng)算出來了。動態(tài)規(guī)劃算法不就是利用過去的結(jié)果解決現(xiàn)在的問題嗎封锉？
這樣绵跷，我們就細(xì)化一下剛才的框架代碼：
int X # 影子狀態(tài)
for 0 <= j < M:
for 0 <= c < 256:
if c == pat[j]:
# 狀態(tài)推進(jìn)
dp[j][c] = j + 1
else:
# 狀態(tài)重啟
# 委托 X 計算重啟位置
dp[j][c] = dp[X][c]
四、代碼實(shí)現(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;
// 當(dāng)前狀態(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] 這個字符才能使?fàn)顟B(tài)從 0 轉(zhuǎn)移到 1脊阴，遇到其它字符的話還是停留在狀態(tài) 0（Java 默認(rèn)初始化數(shù)組全為 0）握侧。
影子狀態(tài) X 是先初始化為 0，然后隨著 j 的前進(jìn)而不斷更新的嘿期。下面看看到底應(yīng)該如何更新影子狀態(tài) X：
int X = 0;
for (int j = 1; j < M; j++) {
...
// 更新影子狀態(tài)
// 當(dāng)前是狀態(tài) X品擎，遇到字符 pat[j]，
// pat 應(yīng)該轉(zhuǎn)移到哪個狀態(tài)备徐？
X = dp[X][pat.charAt(j)];
}
更新 X 其實(shí)和 search 函數(shù)中更新狀態(tài) j 的過程是非常相似的：
int j = 0;
for (int i = 0; i < N; i++) {
// 當(dāng)前是狀態(tài) j萄传，遇到字符 txt[i]，
// pat 應(yīng)該轉(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)脊串，似乎也有一點(diǎn)貼切辫呻。
另外，構(gòu)建 dp 數(shù)組是根據(jù) base case dp[0][..] 向后推演琼锋。這就是我認(rèn)為 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)];
// 到達(dá)終止態(tài)，返回結(jié)果
if (j == M) return i - M + 1;
}
// 沒到達(dá)終止態(tài)念赶，匹配失敗
return -1;
}
}
經(jīng)過之前的詳細(xì)舉例講解础钠，你應(yīng)該可以理解這段代碼的含義了，當(dāng)然你也可以把 KMP 算法寫成一個函數(shù)叉谜。核心代碼也就是兩個函數(shù)中 for 循環(huán)的部分旗吁，數(shù)一下有超過十行嗎？
五停局、最后總結(jié)
傳統(tǒng)的 KMP 算法是使用一個一維數(shù)組 next 記錄前綴信息很钓，而本文是使用一個二維數(shù)組 dp 以狀態(tài)轉(zhuǎn)移的角度解決字符匹配問題，但是空間復(fù)雜度仍然是 O(256M) = O(M)董栽。
在 pat 匹配 txt 的過程中码倦，只要明確了「當(dāng)前處在哪個狀態(tài)」和「遇到的字符是什么」這兩個問題，就可以確定應(yīng)該轉(zhuǎn)移到哪個狀態(tài)（推進(jìn)或回退）锭碳。
對于一個模式串 pat袁稽，其總共就有 M 個狀態(tài)，對于 ASCII 字符擒抛，總共不會超過 256 種推汽。所以我們就構(gòu)造一個數(shù)組 dp[M][256] 來包含所有情況，并且明確 dp 數(shù)組的含義：
dp[j][c] = next 表示歧沪，當(dāng)前是狀態(tài) j歹撒，遇到了字符 c，應(yīng)該轉(zhuǎn)移到狀態(tài) next诊胞。
明確了其含義暖夭，就可以很容易寫出 search 函數(shù)的代碼。
對于如何構(gòu)建這個 dp 數(shù)組撵孤，需要一個輔助狀態(tài) X迈着，它永遠(yuǎn)比當(dāng)前狀態(tài) j 落后一個狀態(tài)，擁有和 j 最長的相同前綴邪码，我們給它起了個名字叫「影子狀態(tài)」寥假。
在構(gòu)建當(dāng)前狀態(tài) j 的轉(zhuǎn)移方向時，只有字符 pat[j] 才能使?fàn)顟B(tài)推進(jìn)（dp[j][pat[j]] = j+1）霞扬；而對于其他字符只能進(jìn)行狀態(tài)回退糕韧，應(yīng)該去請教影子狀態(tài) X 應(yīng)該回退到哪里（dp[j][other] = dp[X][other]枫振，其中 other 是除了 pat[j] 之外所有字符）。
對于影子狀態(tài) X萤彩，我們把它初始化為 0粪滤，并且隨著 j 的前進(jìn)進(jìn)行更新，更新的方式和 search 過程更新 j 的過程非常相似（X = dp[X][pat[j]]）雀扶。
KMP 算法也就是動態(tài)規(guī)劃那點(diǎn)事杖小，我們的公眾號文章目錄有一系列專門講動態(tài)規(guī)劃的，而且都是按照一套框架來的愚墓，無非就是描述問題邏輯予权，明確 dp 數(shù)組含義，定義 base case 這點(diǎn)破事浪册。希望這篇文章能讓大家對動態(tài)規(guī)劃有更深的理解扫腺。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目村象，建議收藏笆环！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星厚者！
