超詳細(xì)!從本質(zhì)上搞懂困惑你多年的KMP匹配算法
來源：知乎
整理：由公眾號“帥地玩編程”整理（已獲授權(quán)）
文章來源于知乎作者洛谷網(wǎng)校 阮行止關(guān)于 kmp 問題的一個解答，已獲作者授權(quán)，本文在他的個人博客的地址：https://ruanx.pw/kmp/
KMP算法是一種字符串匹配算法，可以在 O(n+m) 的時間復(fù)雜度內(nèi)實現(xiàn)兩個字符串的匹配。本文將引導(dǎo)您學(xué)習(xí)KMP算法。
字符串匹配問題
所謂字符串匹配，是這樣一種問題：“字符串 P 是否為字符串 S 的子串？如果是，它出現(xiàn)在 S 的哪些位置？” 其中 S 稱為主串；P 稱為模式串。下面的圖片展示了一個例子。
主串是莎翁那句著名的 “to be or not to be”，這里刪去了空格?！皀o” 這個模式串的匹配結(jié)果是“出現(xiàn)了一次，從S[6]開始”；“ob”這個模式串的匹配結(jié)果是“出現(xiàn)了兩次，分別從s[1]、s[10]開始”。按慣例，主串和模式串都以0開始編號?！ ?/p>
字符串匹配是一個非常頻繁的任務(wù)。例如，今有一份名單，你急切地想知道自己在不在名單上；又如，假設(shè)你拿到了一份文獻(xiàn)，你希望快速地找到某個關(guān)鍵字（keyword）所在的章節(jié)……凡此種種，不勝枚舉?！ ?/p>
我們先從最樸素的Brute-Force算法開始講起。
Brute-Force
顧名思義，Brute-Force是一個純暴力算法。說句題外話，我懷疑，“暴力”一詞在算法領(lǐng)域表示“窮舉、極低效率的實現(xiàn)”，可能就是源于這個英文詞?！ ?/p>
首先，我們應(yīng)該如何實現(xiàn)兩個字符串 A,B 的比較？所謂字符串比較，就是問“兩個字符串是否相等”。最樸素的思想，就是從前往后逐字符比較，一旦遇到不相同的字符，就返回False；如果兩個字符串都結(jié)束了，仍然沒有出現(xiàn)不對應(yīng)的字符，則返回True。實現(xiàn)如下：(python的代碼大致看的懂吧？文末會給出完整的Java和Python代碼)
既然我們可以知道“兩個字符串是否相等”，那么最樸素的字符串匹配算法 Brute-Force 就呼之欲出了——
枚舉 i = 0, 1, 2 … , len(S)-len(P)
將 S[i : i+len(P)] 與 P 作比較。如果一致，則找到了一個匹配?！?/span>
現(xiàn)在我們來模擬 Brute-Force 算法，對主串 “AAAAAABC” 和模式串 “AAAB” 做匹配：
這是一個清晰明了的算法，實現(xiàn)也極其簡單。下面給出Python和C++的實現(xiàn)：
我們成功實現(xiàn)了 Brute-Force 算法?，F(xiàn)在，我們需要對它的時間復(fù)雜度做一點討論。按照慣例，記 n = |S| 為串 S 的長度，m = |P| 為串 P 的長度。
考慮“字符串比較”這個小任務(wù)的復(fù)雜度。最壞情況發(fā)生在：兩個字符串唯一的差別在最后一個字符。這種情況下，字符串比較必須走完整個字符串，才能給出結(jié)果，因此復(fù)雜度是 O(len) 的。
由此，不難想到 Brute-Force 算法所面對的最壞情況：主串形如“AAAAAAAAAAA…B”，而模式串形如“AAAAA…B”。每次字符串比較都需要付出 |P| 次字符比較的代價，總共需要比較 |S| - |P| + 1次，因此總時間復(fù)雜度是 . 考慮到主串一般比模式串長很多，故 Brute-Force 的復(fù)雜度是 ，也就是 O(nm)的。這太慢了！
Brute-Force的改進(jìn)思路
經(jīng)過剛剛的分析，您已經(jīng)看到，Brute-Force 慢得像爬一樣。它最壞的情況如下圖所示：
我們很難降低字符串比較的復(fù)雜度（因為比較兩個字符串，真的只能逐個比較字符）。因此，我們考慮降低比較的趟數(shù)。如果比較的趟數(shù)能降到足夠低，那么總的復(fù)雜度也將會下降很多?！ ∫獌?yōu)化一個算法，首先要回答的問題是“我手上有什么信息？” 我們手上的信息是否足夠、是否有效，決定了我們能把算法優(yōu)化到何種程度。請記住：盡可能利用殘余的信息，是KMP算法的思想所在。
。
在 Brute-Force 中，如果從 S[i] 開始的那一趟比較失敗了，算法會直接開始嘗試從 S[i+1] 開始比較。這種行為，屬于典型的“沒有從之前的錯誤中學(xué)到東西”。我們應(yīng)當(dāng)注意到，一次失敗的匹配，會給我們提供寶貴的信息——如果 S[i : i+len(P)] 與 P 的匹配是在第 r 個位置失敗的，那么從 S[i] 開始的 (r-1) 個連續(xù)字符，一定與 P 的前 (r-1) 個字符一模一樣！
需要實現(xiàn)的任務(wù)是“字符串匹配”，而每一次失敗都會給我們換來一些信息——能告訴我們，主串的某一個子串等于模式串的某一個前綴。但是這又有什么用呢？
跳過不可能成功的字符串比較
有些趟字符串比較是有可能會成功的；有些則毫無可能。我們剛剛提到過，優(yōu)化 Brute-Force 的路線是“盡量減少比較的趟數(shù)”，而如果我們跳過那些絕不可能成功的字符串比較，則可以希望復(fù)雜度降低到能接受的范圍。
那么，哪些字符串比較是不可能成功的？來看一個例子。已知信息如下：
模式串 P = "abcabd".
和主串從S[0]開始匹配時，在 P[5] 處失配。
首先，利用上一節(jié)的結(jié)論。既然是在 P[5] 失配的，那么說明 S[0:5] 等于 P[0:5]，即"abcab". 現(xiàn)在我們來考慮：從 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數(shù)組。
next數(shù)組
next數(shù)組是對于模式串而言的。P 的 next 數(shù)組定義為：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.
如果把模式串視為一把標(biāo)尺，在主串上移動，那么 Brute-Force 就是每次失配之后只右移一位；改進(jìn)算法則是每次失配之后，移很多位，跳過那些不可能匹配成功的位置。但是該如何確定要移多少位呢？
在 S[0] 嘗試匹配，失配于 S[3] <=> P[3] 之后，我們直接把模式串往右移了兩位，讓 S[3] 對準(zhǔn) P[1]. 接著繼續(xù)匹配，失配于 S[8] <=> P[6], 接下來我們把 P 往右平移了三位，把 S[8] 對準(zhǔn) P[3]. 此后繼續(xù)匹配直到成功。
我們應(yīng)該如何移動這把標(biāo)尺？很明顯，如圖中藍(lán)色箭頭所示，舊的后綴要與新的前綴一致（如果不一致，那就肯定沒法匹配上了）！
回憶next數(shù)組的性質(zhì)：P[0] 到 P[i] 這一段子串中，前next[i]個字符與后next[i]個字符一模一樣。既然如此，如果失配在 P[r], 那么P[0]~P[r-1]這一段里面，前next[r-1]個字符恰好和后next[r-1]個字符相等 —— 也就是說，我們可以拿長度為 next[r-1] 的那一段前綴，來頂替當(dāng)前后綴的位置，讓匹配繼續(xù)下去！
您可以驗證一下上面的匹配例子：P[3]失配后，把P[next[3-1]]也就是P[1]對準(zhǔn)了主串剛剛失配的那一位；P[6]失配后，把P[next[6-1]]也就是P[3]對準(zhǔn)了主串剛剛失配的那一位。
如上圖所示，綠色部分是成功匹配，失配于紅色部分。深綠色手繪線條標(biāo)出了相等的前綴和后綴，其長度為next[右端]. 由于手繪線條部分的字符是一樣的，所以直接把前面那條移到后面那條的位置。因此說，next數(shù)組為我們?nèi)绾我苿訕?biāo)尺提供了依據(jù)。接下來，我們實現(xiàn)這個優(yōu)化的算法。
利用next數(shù)組進(jìn)行匹配
了解了利用next數(shù)組加速字符串匹配的原理，我們接下來代碼實現(xiàn)之。分為兩個部分：建立next數(shù)組、利用next數(shù)組進(jìn)行匹配
首先是建立next數(shù)組。我們暫且用最樸素的做法，以后再回來優(yōu)化：
如上圖代碼所示，直接根據(jù)next數(shù)組的定義來建立next數(shù)組。不難發(fā)現(xiàn)它的復(fù)雜度是 [公式] 的
接下來，實現(xiàn)利用next數(shù)組加速字符串匹配。代碼如下：
如何分析這個字符串匹配的復(fù)雜度呢？乍一看，pos值可能不停地變成next[pos-1]，代價會很高；但我們使用攤還分析，顯然pos值一共頂多自增len(S)次，因此pos值減少的次數(shù)不會高于len(S)次。由此，復(fù)雜度是可以接受的，不難分析出整個匹配算法的時間復(fù)雜度：O(n+m).
快速求next數(shù)組
終于來到了我們最后一個問題——如何快速構(gòu)建next數(shù)組。
首先說一句：快速構(gòu)建next數(shù)組，是KMP算法的精髓所在，核心思想是“P自己與自己做匹配”。
為什么這樣說呢？回顧next數(shù)組的完整定義：
定義 “k-前綴” 為一個字符串的前 k 個字符；“k-后綴” 為一個字符串的后 k 個字符。k 必須小于字符串長度。
next[x] 定義為：P[0]~P[x] 這一段字符串，使得k-前綴恰等于k-后綴的最大的k.
這個定義中，不知不覺地就包含了一個匹配——前綴和后綴相等。接下來，我們考慮采用遞推的方式求出next數(shù)組。如果next[0], next[1], … next[x-1]均已知，那么如何求出 next[x] 呢？
來分情況討論。首先，已經(jīng)知道了 next[x-1]（以下記為now），如果 P[x] 與 P[now] 一樣，那最長相等前后綴的長度就可以擴(kuò)展一位，很明顯 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 了。因此，我們應(yīng)該縮短這個now，把它改成小一點的值，再來試試 P[x] 是否等于 P[now].
now該縮小到多少呢？顯然，我們不想讓now縮小太多。因此我們決定，在保持“P[0]~P[x-1]的now-前綴仍然等于now-后綴”的前提下，讓這個新的now盡可能大一點。P[0]~P[x-1] 的公共前后綴，前綴一定落在串A里面、后綴一定落在串B里面。換句話講：接下來now應(yīng)該改成：使得 A的k-前綴等于B的k-后綴的最大的k.
您應(yīng)該已經(jīng)注意到了一個非常強的性質(zhì)——串A和串B是相同的！B的后綴等于A的后綴！因此，使得A的k-前綴等于B的k-后綴的最大的k，其實就是串A的最長公共前后綴的長度 —— next[now-1]！
來看上面的例子。當(dāng)P[now]與P[x]不相等的時候，我們需要縮小now——把now變成next[now-1]，直到P[now]=P[x]為止。P[now]=P[x]時，就可以直接向右擴(kuò)展了。
代碼實現(xiàn)如下
應(yīng)用攤還分析，不難證明構(gòu)建next數(shù)組的時間復(fù)雜度是O(m)的。至此，我們以O(shè)(n+m)的時間復(fù)雜度，實現(xiàn)了構(gòu)建next數(shù)組、利用next數(shù)組進(jìn)行字符串匹配。
以上就是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（點擊閱讀原文直達(dá)，電腦打開更佳）
推薦閱讀
全部文章分類與整理（算法+數(shù)據(jù)結(jié)構(gòu)+計算機基礎(chǔ)），持續(xù)更新
【吐血整理】那些讓你起飛的計算機基礎(chǔ)知識：學(xué)什么，怎么學(xué)？