點擊此處學習更多算法與通信知識

作者 | labuladong

來源 | labuladong

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(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;//?通過?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");?//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?應該轉移到狀態?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?的初始態為?0int?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?+?1else:?#?狀態重啟#?委托?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?casedp[0][pat.charAt(0)]?=?1;//?影子狀態?X?初始為?0int?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 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:]，狀態X總是落后狀態j一個狀態，與j具有最長的相同前綴。所以我把X比喻為影子狀態，似乎也有一點貼切。

另外，構建 dp 數組是根據 base casedp[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?casedp[0][pat.charAt(0)]?=?1;//?影子狀態?X?初始為?0int?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?的初始態為?0int?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 算法支配的恐懼。

六、完整的C++實現

#include <iostream> #include<vector> #include<string> #include <unordered_map> #include <unordered_set> #include <queue> #include <algorithm>//算法頭文件 #include <numeric> #include <stack> #include<typeinfo>#include<stdio.h> using namespace std;class KMP { private:vector<vector<int>> dp;//二維狀態轉移數組string pat;//模式串 public:KMP(string _pat) {pat = _pat;int len = pat.size();//狀態轉移數組dp.resize(len, vector<int>(256));//指定大小后 默認值為0//邊界條件 在0狀態時只有遇到了pat[0]才能轉到狀態1dp[0][(int)pat[0]] = 1;//初始化影子狀態初始值int X = 0;//構建狀態轉移圖for (int j = 1; j < len; j++) {for (int c = 0; c < 256; c++) {if(c != (int)pat[j])dp[j][c] = dp[X][c]; //如果遇到的字符c與j狀態需要進行推進所匹配的字符不匹配時 就狀態重啟到影子狀態elsedp[j][c] = j + 1; //如果遇到的字符c與j狀態需要進行推進所匹配的字符相匹配時 將進行狀態推進//也可以對上面的if進行優化如下面注釋的兩行//dp[j][c] = dp[X][c]; //如果遇到的字符c與j狀態需要進行推進所匹配的字符不匹配時 就狀態重啟到影子狀態//dp[j][(int)pat[j]] = j + 1; //如果遇到的字符c與j狀態需要進行推進所匹配的字符相匹配時 將進行狀態推進}//更新影子狀態X = dp[X][(int)pat[j]];}}int search(string txt) {int len = txt.size();//pat串的初始狀態為0int j = 0;for (int i = 0; i < len; i++) {//計算j的下一個狀態j = dp[j][(int)txt[i]];//如果狀態到達終止態(到pat末尾時)if (j == pat.size()) return i - pat.size() + 1;}//如果遍歷完txt還沒到達終止態則匹配失敗return -1;} };int main() {string pat = "aaab";//ababc aaabstring txt = "aaaaaaab"; //aaaaaaab aaacaaabKMP aa(pat);int pos1 = aa.search(txt);cout << pos1 << endl;system("pause");return 0; }

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

總結

以上是生活随笔為你收集整理的详解KMP算法原理，以及完整java与C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。