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;
        }
        // pat 全都匹配了
        if (j == M) return i;
    }
    // txt 中不存在 pat 子串
    return -1;
}

對於暴力算法，如果出現不匹配字符，同時回退 txt 和 pat 的指針，嵌套 for 循環，時間複雜度  O ( M N ) ，空間複雜度 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 算法就會比較漂亮：

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

KMP kmp = new KMP("aaab");
int pos1 = kmp.search("aaacaaab"); //4
int 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 的過程：

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();
    // 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"，應該轉移到哪裏呢？首先狀態 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: 
            # 狀態重啓
            # 委託 X 計算重啓位置
            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[狀態][字符] = 下個狀態
        dp = new int[M][256];
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子狀態 X 初始爲 0
        int X = 0;
        // 當前狀態 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];
            }
            // 更新影子狀態
            X = dp[X][pat.charAt(j)];
        }
    }

    public int search(String txt) {...}
}

先解釋一下這一行代碼：

// base case
dp[0][pat.charAt(0)] = 1;

這行代碼是 base c ase，只有遇到 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:] ，狀態 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 這點破事。

希望這篇文章能讓大家對動態規劃有更深的理解，並擺脫被 KMP 算法支配的恐懼。