漫畫：什麼是KMP演算法？

作者 | 小灰

————— 第二天 —————

————————————

前情回顧

在字串匹配演算法的前兩講，我們分別介紹了暴力演算法BF演算法，利用雜湊值進行比較的RK演算法，以及儘量減少比較次數的BM演算法，沒看過的小夥伴可以點選下方連結：

1。 BF演算法和RK演算法

2。 BM演算法

如果沒時間細看也沒關係，就讓我帶著大家簡單梳理一下。

首先，給定 “主串” 和 “模式串” 如下：

BF演算法是如何工作的？

正如同它的全稱BruteForce一樣，BF演算法使用簡單粗暴的方式，對主串和模式串進行逐個字元的比較：

第一輪，模式串和主串的第一個等長子串比較，發現第0位字元一致，第1位字元一致，第2位字元不一致：

第二輪，模式串向後挪動一位，和主串的第二個等長子串比較，發現第0位字元不一致：

第三輪，模式串繼續向後挪動一位，和主串的第三個等長子串比較，發現第0位字元不一致：

以此類推，一直到第N輪：

當模式串挪動到某個合適位置，逐個字元比較，發現每一位字元都是匹配時，比較結束：

BF演算法的缺點很明顯，效率實在太低了，每一輪只能老老實實地把模式串右移一位，實際上做了很多無謂的比較。

而BM演算法解決了這一問題。它藉助“壞字元規則”和“好字尾規則”，在每一輪比較時，讓模式串儘可能多移動幾位，減少無謂的比較。

利用BM演算法，上面的主串和模式串匹配只需要比較三輪：

KMP演算法的整體思路

KMP演算法的整體思路是什麼樣子呢？讓我們來看一組例子：

KMP演算法和BF演算法的“開局”是一樣的，同樣是把主串和模式串的首位對齊，從左到右對逐個字元進行比較。

第一輪，模式串和主串的第一個等長子串比較，發現前5個字元都是匹配的，第6個字元不匹配，是一個“壞字元”：

這時候，如何有效利用已匹配的字首 “GTGTG” 呢？

我們可以發現，在字首“GTGTG”當中，後三個字元“GTG”和前三位字元“GTG”是相同的：

在下一輪的比較時，只有把這兩個相同的片段對齊，才有可能出現匹配。這兩個字串片段，分別叫做最長可匹配字尾子串和最長可匹配字首子串。

第二輪，我們直接把模式串向後移動兩位，讓兩個“GTG”對齊，繼續從剛才主串的壞字元A開始進行比較：

顯然，主串的字元A仍然是壞字元，這時候的匹配字首縮短成了GTG：

按照第一輪的思路，我們來重新確定最長可匹配字尾子串和最長可匹配字首子串：

第三輪，我們再次把模式串向後移動兩位，讓兩個“G”對齊，繼續從剛才主串的壞字元A開始進行比較：

以上就是KMP演算法的整體思路：在已匹配的字首當中尋找到最長可匹配字尾子串和最長可匹配字首子串，在下一輪直接把兩者對齊，從而實現模式串的快速移動。

next 陣列

next陣列到底是個什麼鬼呢？這是一個一維整型陣列，陣列的下標代表了“已匹配字首的下一個位置”，元素的值則是“最長可匹配字首子串的下一個位置”。

或許這樣的描述有些晦澀，我們來看一下圖：

當模式串的第一個字元就和主串不匹配時，並不存在已匹配字首子串，更不存在最長可匹配字首子串。這種情況對應的next陣列下標是0，next［0］的元素值也是0。

如果已匹配字首是G、GT、GTGTGC，並不存在最長可匹配字首子串，所以對應的next陣列元素值（next［1］，next［2］，next［6］）同樣是0。

GTG的最長可匹配字首是G，對應陣列中的next［3］，元素值是1。

以此類推，

GTGT 對應 next［4］，元素值是2。

GTGTG 對應 next［5］，元素值是3。

有了next陣列，我們就可以透過已匹配字首的下一個位置（壞字元位置），快速尋找到最長可匹配字首的下一個位置，然後把這兩個位置對齊。

比如下面的場景，我們透過壞字元下標5，可以找到next［5］=3，即最長可匹配字首的下一個位置：

說完了next陣列是什麼，接下來我們再來思考一下，如何事先生成這個next陣列呢？

由於已匹配字首陣列在主串和模式串當中是相同的，所以我們僅僅依據模式串，就足以生成next陣列。

最簡單的方法是從最長的字首子串開始，把每一種可能情況都做一次比較。

假設模式串的長度是m，生成next陣列所需的最大總比較次數是1+2+3+4+……+m-2 次。

顯然，這種方法的效率非常低，如何進行最佳化呢？

我們可以採用類似“動態規劃”的方法。首先next［0］和next［1］的值肯定是0，因為這時候不存在字首子串；從next［2］開始，next陣列的每一個元素都可以由上一個元素推導而來。

已知next［i］的值，如何推匯出next［i+1］呢？讓我們來演示一下上述next陣列的填充過程：

如圖所示，我們設定兩個變數i和j，其中i表示“已匹配字首的下一個位置”，也就是待填充的陣列下標，j表示“最長可匹配字首子串的下一個位置”，也就是待填充的陣列元素值。

當已匹配字首不存在的時候，最長可匹配字首子串當然也不存在，所以i=0，j=0，此時next［0］ = 0。

接下來，我們讓已匹配字首子串的長度加1：

此時的已匹配字首是G，由於只有一個字元，同樣不存在最長可匹配字首子串，所以i=1，j=0，next［1］ = 0。

接下來，我們讓已匹配字首子串的長度繼續加1：

此時的已匹配字首是GT，我們需要開始做判斷了：由於模式串當中 pattern［j］ ！= pattern［i-1］，即G！=T，最長可匹配字首子串仍然不存在。

所以當i=2時，j仍然是0，next［2］ = 0。

接下來，我們讓已匹配字首子串的長度繼續加1：

此時的已匹配字首是GTG，由於模式串當中 pattern［j］ = pattern［i-1］，即G=G，最長可匹配字首子串出現了，是G。

所以當i=3時，j=1，next［3］ = next［2］+1 = 1。

接下來，我們讓已匹配字首子串的長度繼續加1：

此時的已匹配字首是GTGT，由於模式串當中 pattern［j］ = pattern［i-1］，即T=T，最長可匹配字首子串又增加了一位，是GT。

所以當i=4時，j=2，next［4］ = next［3］+1 = 2。

接下來，我們讓已匹配字首子串的長度繼續加1：

此時的已匹配字首是GTGTG，由於模式串當中 pattern［j］ = pattern［i-1］，即G=G，最長可匹配字首子串又增加了一位，是GTG。

所以當i=5時，j=3，next［5］ = next［4］+1 = 3。

接下來，我們讓已匹配字首子串的長度繼續加1：

此時的已匹配字首是GTGTGC，這時候需要注意了，模式串當中 pattern［j］ ！= pattern［i-1］，即T ！= C，這時候該怎麼辦呢？

這時候，我們已經無法從next［5］的值來推匯出next［6］，而字元C的前面又有兩段重複的子串“GTG”。那麼，我們能不能把問題轉化一下？

或許聽起來有些繞：我們可以把計算“GTGTGC”最長可匹配字首子串的問題，轉化成計算“GTGC”最長可匹配字首子串的問題。

這樣的問題轉化，也就相當於把變數j回溯到了next［j］，也就是j=1的局面（i值不變）：

回溯後，情況仍然是 pattern［j］ ！= pattern［i-1］，即T！=C。那麼我們可以把問題繼續進行轉化：

問題再次的轉化，相當於再一次把變數j回溯到了next［j］，也就是j=0的局面：

回溯後，情況仍然是 pattern［j］ ！= pattern［i-1］，即G！=C。j已經不能再次回溯了，所以我們得出結論：i=6時，j=0，next［6］ = 0。

以上就是next陣列元素的推導過程。

1。 對模式串預處理，生成next陣列

2。 進入主迴圈，遍歷主串

2。1。 比較主串和模式串的字元

2。2。 如果發現壞字元，查詢next陣列，得到匹配字首所對應的最長可匹配字首子串，移動模式串到對應位置

2。3。如果當前字元匹配，繼續迴圈

KMP演算法的具體實現

// KMP演算法主體邏輯。str是主串，pattern是模式串

publicstaticintkmp（String str， String pattern） {

//預處理，生成next陣列

int［］ next = getNexts（pattern）；

int j = 0；

//主迴圈，遍歷主串字元

for （int i = 0； i < str。length（）； i++） {

while （j > 0 && str。charAt（i） ！= pattern。charAt（j）） {

//遇到壞字元時，查詢next陣列並改變模式串的起點

j = next［j］；

}

if （str。charAt（i） == pattern。charAt（j）） {

j++；

}

if （j == pattern。length（）） {

//匹配成功，返回下標

return i - pattern。length（） + 1；

}

}

return-1；

}

// 生成Next陣列

privatestaticint［］ getNexts（String pattern） {

int［］ next = newint［pattern。length（）］；

int j = 0；

for （int i=2； i

while （j ！= 0 && pattern。charAt（j） ！= pattern。charAt（i-1）） {

//從next［i+1］的求解回溯到 next［j］

j = next［j］；

}

if （pattern。charAt（j） == pattern。charAt（i-1）） {

j++；

}

next［i］ = j；

}

return next；

}

publicstaticvoidmain（String［］ args） {

String str = “ATGTGAGCTGGTGTGTGCFAA”；

String pattern = “GTGTGCF”；

int index = kmp（str， pattern）；

System。out。println（“首次出現位置：” + index）；

}

【End】

阿里大牛：

華先勝、丁險峰直播分享！

今晚7點

，阿里巴巴集團

副總裁華先勝

——《

人工智慧：

是風、是雲，還是雨？

》

面向開發者詳解視覺智慧技術規模化落地的挑戰；面向企業詳述如何透過核心AI技術、產品化 及平臺化實現客戶價值並構建壁壘？