動態規劃之KMP字符匹配算法

文章目錄

• 動態規劃之KMP字符匹配算法
• • 一、問題引入
  • 二、 KMP 算法概述
  • 三、 狀態機概述
  • 四、 構建狀態轉移圖
  • 五、 代碼實現
  • 六、 最后總結

本文的KMP算法是通過狀態機的改進版本，普通的KMP實現方法請點擊：👇
https://blog.csdn.net/wolfGuiDao/article/details/108299448

一、問題引入

KMP 算法（Knuth-Morris-Pratt 算法） 是?個著名的字符串匹配算法， 效率很?， 但是確實有點復雜。

先在開頭約定， 本?? pat 表?模式串， ?度為 M ， txt 表??本串，?度為 N 。 KMP 算法是在 txt 中查找?串 pat ， 如果存在， 返回這個?串的起始索引， 否則返回 -1。

讀者?過的 KMP 算法應該是， ?波詭異的操作處理 pat 后形成?個?維的數組 next ， 然后根據這個數組經過??波復雜操作去匹配 txt 。 時間復雜度 O(N)， 空間復雜度 O(M)。

其實它這個 next 數組就相當于 dp 數組， 其中元素的含義跟 pat 的前綴和后綴有關， 判定規則?較復雜， 不好理解。 本?則??個?維的 dp 數組（但空間復雜度還是 O(M)） ， 重新定義其中元素的含義， 使得代碼?度??減少， 可解釋性??提?。

二、 KMP 算法概述

?先還是簡單介紹?下 KMP 算法和暴?匹配算法的不同在哪?， 難點在哪?， 和動態規劃有啥關系。

暴?的字符串匹配算法很容易寫， 看?下它的運?邏輯：

// 暴?匹配（偽碼） int search(String pat, String txt) {int M = pat.length;int N = txt.length;for (int i = 0; i <= N - M; i++) {for (int 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 這樣移動：

這個 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

• 代碼描述：

#include <iostream> #include <string> #include <vector> using namespace std;vector<int> GetNext(string& match) {vector<int> next(match.size() + 1,0);next[0] = -1;int i = 2;int k = 0;while(i < match.size()){if(match[i - 1] == match[k]){next[i] = k + 1;k = next[i];i++;}else if(k == -1){next[i] = 0;i++;}else {k = next[k];}}return next; }int main() {string str;string match;while(getline(cin,str)){getline(cin,match);vector<int> next = GetNext(match);int flag = 1;int i = 0;int j = 0;while(i < str.size()){if(str[i] == match[j]){i++;j++;if(j == match.size()){flag = 0;cout<<i - match.size()<<" ";j = next[j];}}else{j = next[j];if(j == -1){j = 0;i++;}}}if(flag)cout<<-1<<endl;}return 0; }

三、 狀態機概述

為什么說 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 算法最關鍵的步驟就是構造這個狀態轉移圖 。

要確定狀態轉移的?為， 得明確兩個變量， ?個是當前的匹配狀態， 另?個是遇到的字符；確定了這兩個變量后， 就可以知道這個情況下應該轉移到哪個狀態。

為了描述狀態轉移圖， 我們定義?個?維 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 數組就是我們剛才畫的那幅狀態轉移圖，

四、 構建狀態轉移圖

重重重點又來了！如何構建狀態轉移圖？？？

要確定狀態轉移的?為， 必須明確兩個變量， ?個是當前的
匹配狀態， 另?個是遇到的字符， ?且我們已經根據這個邏輯確定了 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 + 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;elsedp[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..end] ， 狀態X 總是落后狀態 j ?個狀態， 與 j 具有最?的相同前綴。 所以我把 X?喻為影?狀態， 似乎也有?點貼切。另外， 構建 dp 數組是根據 base case dp[0][…] 向后推演。 這就是我認為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;} }

C++代碼

//封裝一個KMP算法用來快速查找字符串匹配 class KMP {public:KMP(const std::string& pat):_pat(pat){int M = _pat.size();//dp[狀態][字符] = 下一個狀態；把dp初始化為全0dp = std::vector<std::vector<int>>(M,std::vector<int>(256,0));//base case ：一開始dp中存的是0，那么規定最開始為0狀態，遇到第一個字符為pat轉換為1狀態dp[0][_pat[0]] = 1;//博客中說的影子狀態，初始化為0狀態int X = 0;//開始循環構造狀態轉換圖即dpfor(int j = 1;j < M;j++){for(int c = 0;c < 256;c++){dp[j][c] = dp[X][c];}dp[j][_pat[j]] = j + 1;//更新影子狀態X = dp[X][_pat[j]];}}int Search(const std::string& txt){int M = _pat.size();int N = txt.size();//pat的初始狀態為0狀態int j = 0;//循環for(int i = 0;i < N;i++){j = dp[j][txt[i]];//如果經過狀態轉換圖dp可以到達終態M，就說明在txt中成功找到匹配的字符串，直接返回其在txt中的下標索引if(j == M){return i - M + 1;}}//代碼走到這里代表遍歷完txt還沒有找到匹配的return出去，就直接return -1；return -1;}private://dp存放狀態轉換圖;dp[1]['A'] = 2;代表 狀態1 如果遇到字符'A'，pat 就轉換為2狀態std::vector<std::vector<int>> dp;//用戶輸入pat待匹配的字符串std::string _pat; };

六、 最后總結

傳統的 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字符匹配算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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