動態規劃之 KMP 算法詳解
摘要:在 pat 匹配 txt 的過程中,只要明確了「 當前處在哪個狀態 」和「 遇到的字符是什麼 」這兩個問題,就可以確定應該轉移到哪個狀態(推進或回退)。傳統的 KMP 算法是使用一個一維數組 next 記錄前綴信息,而本文是使用一個二維數組 dp 以狀態轉移的角度解決字符匹配問題,但是空間複雜度仍然是 O(256M) = O(M)。
預計閱讀時間:15 分鐘
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 循環,時間複雜度 ,空間複雜度 。最主要的問題是,如果字符串中重複的字符比較多,該算法就顯得很蠢。
比如 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 算法就會比較漂亮:
這樣,當我們需要用同一 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 算法支配的恐懼。