超詳細！從本質上搞懂困惑你多年的KMP匹配算法

• 2020 年 3 月 4 日
• 筆記

來源：知乎

整理：由公眾號「帥地玩編程」整理（已獲授權）

文章來源於知乎作者洛谷網校 阮行止關於 kmp 問題的一個解答，已獲作者授權，本文在他的個人博客的地址：https://ruanx.pw/kmp/

KMP算法是一種字符串匹配算法，可以在 O(n+m) 的時間複雜度內實現兩個字符串的匹配。本文將引導您學習KMP算法。

字符串匹配問題

所謂字符串匹配，是這樣一種問題：「字符串 P 是否為字符串 S 的子串？如果是，它出現在 S 的哪些位置？」 其中 S 稱為主串；P 稱為模式串。下面的圖片展示了一個例子。

主串是莎翁那句著名的 「to be or not to be」，這裡刪去了空格。「no」 這個模式串的匹配結果是「出現了一次，從S[6]開始」；「ob」這個模式串的匹配結果是「出現了兩次，分別從s[1]、s[10]開始」。按慣例，主串和模式串都以0開始編號。　　

字符串匹配是一個非常頻繁的任務。例如，今有一份名單，你急切地想知道自己在不在名單上；又如，假設你拿到了一份文獻，你希望快速地找到某個關鍵字（keyword）所在的章節……凡此種種，不勝枚舉。　　

我們先從最樸素的Brute-Force算法開始講起。

Brute-Force　　

顧名思義，Brute-Force是一個純暴力算法。說句題外話，我懷疑，「暴力」一詞在算法領域表示「窮舉、極低效率的實現」，可能就是源於這個英文詞。　　

首先，我們應該如何實現兩個字符串 A,B 的比較？所謂字符串比較，就是問「兩個字符串是否相等」。最樸素的思想，就是從前往後逐字符比較，一旦遇到不相同的字符，就返回False；如果兩個字符串都結束了，仍然沒有出現不對應的字符，則返回True。實現如下：(python的代碼大致看的懂吧？文末會給出完整的Java和Python代碼)

既然我們可以知道「兩個字符串是否相等」，那麼最樸素的字符串匹配算法 Brute-Force 就呼之欲出了——

• 枚舉 i = 0, 1, 2 … , len(S)-len(P)
• 將 S[i : i+len(P)] 與 P 作比較。如果一致，則找到了一個匹配。　

現在我們來模擬 Brute-Force 算法，對主串 「AAAAAABC」 和模式串 「AAAB」 做匹配：

這是一個清晰明了的算法，實現也極其簡單。下面給出Python和C++的實現：

我們成功實現了 Brute-Force 算法。現在，我們需要對它的時間複雜度做一點討論。按照慣例，記 n = |S| 為串 S 的長度，m = |P| 為串 P 的長度。

考慮「字符串比較」這個小任務的複雜度。最壞情況發生在：兩個字符串唯一的差別在最後一個字符。這種情況下，字符串比較必須走完整個字符串，才能給出結果，因此複雜度是 O(len) 的。

由此，不難想到 Brute-Force 算法所面對的最壞情況：主串形如「AAAAAAAAAAA…B」，而模式串形如「AAAAA…B」。每次字符串比較都需要付出 |P| 次字符比較的代價，總共需要比較 |S| – |P| + 1次，因此總時間複雜度是 . 考慮到主串一般比模式串長很多，故 Brute-Force 的複雜度是 ，也就是 O(nm)的。這太慢了！

Brute-Force的改進思路

經過剛剛的分析，您已經看到，Brute-Force 慢得像爬一樣。它最壞的情況如下圖所示：

我們很難降低字符串比較的複雜度（因為比較兩個字符串，真的只能逐個比較字符）。因此，我們考慮降低比較的趟數。如果比較的趟數能降到足夠低，那麼總的複雜度也將會下降很多。　　要優化一個算法，首先要回答的問題是「我手上有什麼信息？」　我們手上的信息是否足夠、是否有效，決定了我們能把算法優化到何種程度。請記住：儘可能利用殘餘的信息，是KMP算法的思想所在。 。

在 Brute-Force 中，如果從 S[i] 開始的那一趟比較失敗了，算法會直接開始嘗試從 S[i+1] 開始比較。這種行為，屬於典型的「沒有從之前的錯誤中學到東西」。我們應當注意到，一次失敗的匹配，會給我們提供寶貴的信息——如果 S[i : i+len(P)] 與 P 的匹配是在第 r 個位置失敗的，那麼從 S[i] 開始的 (r-1) 個連續字符，一定與 P 的前 (r-1) 個字符一模一樣！

需要實現的任務是「字符串匹配」，而每一次失敗都會給我們換來一些信息——能告訴我們，主串的某一個子串等於模式串的某一個前綴。但是這又有什麼用呢？

跳過不可能成功的字符串比較

有些趟字符串比較是有可能會成功的；有些則毫無可能。我們剛剛提到過，優化 Brute-Force 的路線是「盡量減少比較的趟數」，而如果我們跳過那些絕不可能成功的字符串比較，則可以希望複雜度降低到能接受的範圍。

那麼，哪些字符串比較是不可能成功的？來看一個例子。已知信息如下：

• 模式串 P = "abcabd".
• 和主串從S[0]開始匹配時，在 P[5] 處失配。

首先，利用上一節的結論。既然是在 P[5] 失配的，那麼說明 S[0:5] 等於 P[0:5]，即"abcab". 現在我們來考慮：從 S[1]、S[2]、S[3] 開始的匹配嘗試，有沒有可能成功？　　

從 S[1] 開始肯定沒辦法成功，因為 S[1] = P[1] = 'b'，和 P[0] 並不相等。從 S[2] 開始也是沒戲的，因為 S[2] = P[2] = 'c'，並不等於P[0]. 但是從 S[3] 開始是有可能成功的——至少按照已知的信息，我們推不出矛盾。

帶着「跳過不可能成功的嘗試」的思想，我們來看next數組。

next數組

next數組是對於模式串而言的。P 的 next 數組定義為：next[i] 表示 P[0] ~ P[i] 這一個子串，使得 前k個字符恰等於後k個字符的最大的k. 特別地，k不能取i+1（因為這個子串一共才 i+1 個字符，自己肯定與自己相等，就沒有意義了）。

上圖給出了一個例子。P="abcabd"時，next[4]=2，這是因為P[0] ~ P[4] 這個子串是"abcab"，前兩個字符與後兩個字符相等，因此next[4]取2. 而next[5]=0，是因為"abcabd"找不到前綴與後綴相同，因此只能取0.

如果把模式串視為一把標尺，在主串上移動，那麼 Brute-Force 就是每次失配之後只右移一位；改進算法則是每次失配之後，移很多位，跳過那些不可能匹配成功的位置。但是該如何確定要移多少位呢？

在 S[0] 嘗試匹配，失配於 S[3] <=> P[3] 之後，我們直接把模式串往右移了兩位，讓 S[3] 對準 P[1]. 接着繼續匹配，失配於 S[8] <=> P[6], 接下來我們把 P 往右平移了三位，把 S[8] 對準 P[3]. 此後繼續匹配直到成功。

我們應該如何移動這把標尺？很明顯，如圖中藍色箭頭所示，舊的後綴要與新的前綴一致（如果不一致，那就肯定沒法匹配上了）！

回憶next數組的性質：P[0] 到 P[i] 這一段子串中，前next[i]個字符與後next[i]個字符一模一樣。既然如此，如果失配在 P[r], 那麼P[0]~P[r-1]這一段裏面，前next[r-1]個字符恰好和後next[r-1]個字符相等 —— 也就是說，我們可以拿長度為 next[r-1] 的那一段前綴，來頂替當前後綴的位置，讓匹配繼續下去！

您可以驗證一下上面的匹配例子：P[3]失配後，把P[next[3-1]]也就是P[1]對準了主串剛剛失配的那一位；P[6]失配後，把P[next[6-1]]也就是P[3]對準了主串剛剛失配的那一位。

如上圖所示，綠色部分是成功匹配，失配於紅色部分。深綠色手繪線條標出了相等的前綴和後綴，其長度為next[右端]. 由於手繪線條部分的字符是一樣的，所以直接把前面那條移到後面那條的位置。因此說，next數組為我們如何移動標尺提供了依據。接下來，我們實現這個優化的算法。

利用next數組進行匹配

了解了利用next數組加速字符串匹配的原理，我們接下來代碼實現之。分為兩個部分：建立next數組、利用next數組進行匹配

首先是建立next數組。我們暫且用最樸素的做法，以後再回來優化：

如上圖代碼所示，直接根據next數組的定義來建立next數組。不難發現它的複雜度是 [公式] 的

接下來，實現利用next數組加速字符串匹配。代碼如下：

如何分析這個字符串匹配的複雜度呢？乍一看，pos值可能不停地變成next[pos-1]，代價會很高；但我們使用攤還分析，顯然pos值一共頂多自增len(S)次，因此pos值減少的次數不會高於len(S)次。由此，複雜度是可以接受的，不難分析出整個匹配算法的時間複雜度：O(n+m).

快速求next數組

終於來到了我們最後一個問題——如何快速構建next數組。

首先說一句：快速構建next數組，是KMP算法的精髓所在，核心思想是「P自己與自己做匹配」。

為什麼這樣說呢？回顧next數組的完整定義：

• 定義 「k-前綴」 為一個字符串的前 k 個字符；「k-後綴」 為一個字符串的後 k 個字符。k 必須小於字符串長度。
• next[x] 定義為：P[0]~P[x] 這一段字符串，使得k-前綴恰等於k-後綴的最大的k.

這個定義中，不知不覺地就包含了一個匹配——前綴和後綴相等。接下來，我們考慮採用遞推的方式求出next數組。如果next[0], next[1], … next[x-1]均已知，那麼如何求出 next[x] 呢？

來分情況討論。首先，已經知道了 next[x-1]（以下記為now），如果 P[x] 與 P[now] 一樣，那最長相等前後綴的長度就可以擴展一位，很明顯 next[x] = now + 1. 圖示如下。

剛剛解決了 P[x] = P[now] 的情況。那如果 P[x] 與 P[now] 不一樣，又該怎麼辦？

如圖。長度為 now 的子串 A 和子串 B 是 P[0]~P[x-1] 中最長的公共前後綴。可惜 A 右邊的字符和 B 右邊的那個字符不相等，next[x]不能改成 now+1 了。因此，我們應該縮短這個now，把它改成小一點的值，再來試試 P[x] 是否等於 P[now].

now該縮小到多少呢？顯然，我們不想讓now縮小太多。因此我們決定，在保持「P[0]~P[x-1]的now-前綴仍然等於now-後綴」的前提下，讓這個新的now儘可能大一點。P[0]~P[x-1] 的公共前後綴，前綴一定落在串A裏面、後綴一定落在串B裏面。換句話講：接下來now應該改成：使得 A的k-前綴等於B的k-後綴的最大的k.

您應該已經注意到了一個非常強的性質——串A和串B是相同的！B的後綴等於A的後綴！因此，使得A的k-前綴等於B的k-後綴的最大的k，其實就是串A的最長公共前後綴的長度 —— next[now-1]！

來看上面的例子。當P[now]與P[x]不相等的時候，我們需要縮小now——把now變成next[now-1]，直到P[now]=P[x]為止。P[now]=P[x]時，就可以直接向右擴展了。

代碼實現如下

應用攤還分析，不難證明構建next數組的時間複雜度是O(m)的。至此，我們以O(n+m)的時間複雜度，實現了構建next數組、利用next數組進行字符串匹配。

以上就是KMP算法。它於1977年被提出，全稱 Knuth–Morris–Pratt 算法。讓我們記住前輩們的名字：Donald Knuth(K), James H. Morris(M), Vaughan Pratt(P).

最後附上洛谷P3375 KMP字符串匹配 的Python和Java版代碼：

給大家推薦一個Github，裏面有好幾百本CS類地常用電子書，推薦給大家：https://github.com/iamshuaidi/CS-Book