資料結構與演算法之美 | 別怕，有我！KMP 演算法詳解

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 陣列的名稱。特別地，本篇文章轉載自labuladong。

一、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； } // pat 全都匹配了 if （j == M） return i； } // txt 中不存在 pat 子串 return -1；}

對於暴力演算法，如果出現不匹配字元，同時回退 txt 和 pat 的指標，巢狀 for 迴圈，時間複雜度 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 陣列中儲存的資訊把 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； // 透過 pat 構建 dp 陣列 // 需要 O（M）時間 } public int search（String txt） { // 藉助 dp 陣列去匹配 txt // 需要 O（N）時間 }}

這樣，當我們需要用同一 pat 去匹配不同 txt 時，就不需要浪費時間構造 dp 陣列了：

KMP kmp = new KMP（“aaab”）；int pos1 = kmp。search（“aaacaaab”）； //4int pos2 = kmp。search（“aaaaaaab”）； //4

二、狀態機概述

為什麼說 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 的過程：

請記住這個 GIF 的匹配過程，這就是 KMP 演算法的核心邏輯！

為了描述狀態轉移圖，我們定義一個二維 dp 陣列，它的含義如下：

dp［j］［c］ = next0 <= j < M，代表當前的狀態0 <= c < 256，代表遇到的字元（ASCII 碼）0 <= next <= M，代表下一個狀態dp［4］［‘A’］ = 3 表示：當前是狀態 4，如果遇到字元 A，pat 應該轉移到狀態 3dp［1］［‘B’］ = 2 表示：當前是狀態 1，如果遇到字元 B，pat 應該轉移到狀態 2

根據我們這個 dp 陣列的定義和剛才狀態轉移的過程，我們可以先寫出 KMP 演算法的 search 函式程式碼：

public int search（String txt） { int M = pat。length（）； int N = txt。length（）； // pat 的初始態為 0 int j = 0； for （int i = 0； i < N； i++） { // 當前是狀態 j，遇到字元 txt［i］， // pat 應該轉移到哪個狀態？ 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”，應該轉移到哪裡呢？首先只有遇到 “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 如何轉移，在之前就已經算出來了。動態規劃演算法不就是利用過去的結果解決現在的問題嗎？

這樣，我們就細化一下剛才的框架程式碼：

int X # 影子狀態for 0 <= j < M： for 0 <= c < 256： if c == pat［j］： # 狀態推進 dp［j］［c］ = j + 1 else： # 狀態重啟 # 委託 X 計算重啟位置 dp［j］［c］ = dp［X］［c］

四、程式碼實現

如果之前的內容你都能理解，恭喜你，現在就剩下一個問題：影子狀態 X 是如何得到的呢？下面先直接看完整程式碼吧。

先解釋一下這一行程式碼：

// base casedp［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，遇到字元 pat［j］， // pat 應該轉移到哪個狀態？ X = dp［X］［pat。charAt（j）］；}

更新 X 其實和 search 函式中更新狀態 j 的過程是非常相似的：

int j = 0；for （int i = 0； i < N； i++） { // 當前是狀態 j，遇到字元 txt［i］， // pat 應該轉移到哪個狀態？ j = dp［j］［txt。charAt（i）］；。。。}

其中的原理非常微妙，

注意程式碼中 for 迴圈的變數初始值，可以這樣理解：後者是在 txt 中匹配 pat，前者是在 pat 中匹配 pat［1…end］，狀態 X 總是落後狀態 j 一個狀態，與 j 具有最長的相同字首。所以我把 X 比喻為影子狀態，似乎也有一點貼切。

另外，構建 dp 陣列是根據 base case dp［0］［…］向後推演。這就是我認為 KMP 演算法就是一種動態規劃演算法的原因。

下面來看一下狀態轉移圖的完整構造過程，你就能理解狀態 X 作用之精妙了：

至此，KMP 演算法的核心終於寫完啦啦啦啦！看下 KMP 演算法的完整程式碼吧：

public class KMP { private int［］［］ dp； private String pat； public KMP（String pat） { this。pat = pat； int M = pat。length（）； // dp［狀態］［字元］ = 下個狀態 dp = new int［M］［256］； // base case dp［0］［pat。charAt（0）］ = 1； // 影子狀態 X 初始為 0 int X = 0； // 構建狀態轉移圖（稍改的更緊湊了） 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； // 更新影子狀態 X = dp［X］［pat。charAt（j）］； } } public int search（String txt） { int M = pat。length（）； int N = txt。length（）； // pat 的初始態為 0 int j = 0； for （int i = 0； i < N； i++） { // 計算 pat 的下一個狀態 j = dp［j］［txt。charAt（i）］； // 到達終止態，返回結果 if （j == M） return i - M + 1； } // 沒到達終止態，匹配失敗 return -1； }}

經過之前的詳細舉例講解，你應該可以理解這段程式碼的含義了，當然你也可以把 KMP 演算法寫成一個函式。核心程式碼也就是兩個函式中 for 迴圈的部分，數一下有超過十行嗎？

五、最後總結

傳統的 KMP 演算法是使用一個一維陣列 next 記錄字首資訊，而本文是使用一個二維陣列 dp 以狀態轉移的角度解決字元匹配問題，但是空間複雜度仍然是 O（256M） = O（M）。

在 pat 匹配 txt 的過程中，只要明確了「當前處在哪個狀態」和「遇到的字元是什麼」這兩個問題，就可以確定應該轉移到哪個狀態（推進或回退）。

對於一個模式串 pat，其總共就有 M 個狀態，對於 ASCII 字元，總共不會超過 256 種。所以我們就構造一個數組 dp［M］［256］來包含所有情況，並且明確 dp 陣列的含義：

dp［j］［c］ = next 表示，當前是狀態 j，遇到了字元 c，應該轉移到狀態 next。

明確了其含義，就可以很容易寫出 search 函式的程式碼。

對於如何構建這個 dp 陣列，需要一個輔助狀態 X，它永遠比當前狀態 j 落後一個狀態，擁有和 j 最長的相同字首，我們給它起了個名字叫「影子狀態」。

在構建當前狀態 j 的轉移方向時，只有字元 pat［j］才能使狀態推進（dp［j］［pat［j］］ = j+1）；而對於其他字元只能進行狀態回退，應該去請教影子狀態 X 應該回退到哪裡（dp［j］［other］ = dp［X］［other］，其中 other 是除了 pat［j］之外所有字元）。

對於影子狀態 X，我們把它初始化為 0，並且隨著 j 的前進進行更新，更新的方式和 search 過程更新 j 的過程非常相似（X = dp［X］［pat［j］］）。

KMP 演算法也就是動態規劃那點事，我們的公眾號文章目錄有一系列專門講動態規劃的，而且都是按照一套框架來的，無非就是描述問題邏輯，明確 dp 陣列含義，定義 base case 這點破事。希望這篇文章能讓大家對動態規劃有更深的理解。

如果本文對你有幫助，歡迎關注我的公眾號：