徹底理解字符串匹配 KMP 算法

大家好，我是小風哥，今天簡單聊聊字符串匹配 kmp 算法。

字符串匹配是計算機科學中非常基礎的操作，給定兩個字符串 a 和 b，我們需要判斷字符串 a 是否包含字符串 b。

像你我這樣的普通程序員能想到的最簡單方法是這樣的，用字符串 b 不斷去匹配每個主串中的子串。

假設給定這樣兩個字符串：

首先從主串的第一個位置和子串的第一個位置去匹配，我們發現 A 和 B 不相同：

因此主串指針後移一位，子串重新從最第一個字符開始匹配。

這時我們發現 A 和 C 不同，因此匹配失敗。

主串指針回退到第三個字符，子串重新從第一個字符開始匹配。

此時 B 和 A 又不同，重複上述過程。

這次成功找到多個相同的字符，但最後一個字符匹配失敗：

按照我們的算法，主串指針需要回退到第 5 個字符重新匹配。

這就是你我這種肉體凡胎能想到的算法，時間複雜度是 O(mn)，效率低下的原因當然是主串指針需要回退。

然而有三位大神不是這麼想的，它們跳出來凡人的思考方式發明了一種極具創意的算法，由於是三個人同時發現，因此這個算法取了三人名字的首字母，這就是著名的 kmp 算法。

看到這裏相信你就能明白爲什麼這個算法很難掌握了吧，難是正常的，覺得不難纔不正常，如果你能無師自通搞定 kmp 算法，那麼早出生幾十年你也能和大師們並駕齊驅供我等凡夫俗子瞻仰。

廢話不多說，接下來就讓我們領略一下大師的非凡境界。

注意看這個主串指針，大師們思考的第一個問題就是，主串指針是否有必要回退，這是最關鍵最核心的問題。

讓我們回到剛纔部分匹配的示例。

主串指針是否需要需要回退呢？我們思考兩種可能。

第一種可能，即使能匹配成功，匹配成功的起始位置也在主串指針 H 及以後，在這種情況下主串指針不需要回退。

第二種可能，匹配成功的起始位置經過主串指針 H：

在這種情況下，主串指針之前的兩個字符 A 和 B 一定是成功匹配了的：此時我們只需要比較主串指針 H 及以後的位置即可。

只有這麼兩種可能。

因此可以看到，主串指針根本就沒有必要回退。

現在我們知道了主串指針不需要回退，那麼子串指針該從哪裏開始匹配呢？從頭開始嗎？

注意看我們剛纔提到的第二種可能，匹配成功的起始位置經過主串指針 H，在這種情況下，主串指針之前的兩個字符 A 和 B 一定是成功匹配了的，這意味着什麼呢？

這意味着 AB 是這個字符串的後綴：

AB 是這個字符串的前綴：

不要忘了這兩個字符串是成功匹配了的：

也就是說這是兩個完全相同的字符串，這就意味着 AB 是成功匹配字符串的相同前後綴。

這樣子符串指針也不需要回退到起始位置，而是從共同前後綴的下一個位置開始匹配即可。

而對於部分匹配的子串根本不存在共同前後綴的情況，

我們直接從子串起始位置進行匹配。

可以看到，由於主串指針不回退，這大幅提高了算法的效率。

想要實現這樣的算法，關鍵是怎樣計算出部分匹配子串的共同前後綴。

因此我們來到了第二個核心問題。

我們以 ABCDAB 爲例來講解。

這是長度爲 1 的前後綴，這是長度爲 2 的前後綴，以此類推。

可以看到，在所有的前後綴中，相同前後綴的最大長度是 2。

我們記下來。

實際上我們需要把所有子串的相同前後綴都計算出來。

對於 ABCDA 這個子串來說，相同前後綴長度是 1，因爲兩個 A 是相同前後綴。

而對於 ABCD 這個子串來說，相同前後綴的長度是 0，也就是沒有相同的前後綴。

其它也一樣。

這樣我們就到了一個數組，通過查找這個數組我們能知道任意子串的共同前後綴長度。

這個數組在很多資料中被稱之爲 next 數組。

有了 next 數組就簡單了。

假設此時我們發現兩個指針指向的字符不同，接下來只需要簡單查找 next 數組：

發現已匹配部分的相同前後綴長度是 2：

因此主指針不動，子串指針移動到相同前後綴的下一個位置繼續去匹配即可。

可以看到，只要我們能得到 next 數組，就可以在線性時間複雜度內解決問題。

這裏，我們來到了第三個核心問題，那就是該怎樣高效計算出 next 數組。

假設此時我們已經計算出了這個子串的共同前後綴，也就是長度爲 n 的這兩個部分。

接下來計算下一個位置的最長前後綴，我們只需要分別後移兩個指針，然後比較字符是否相等，這裏有兩種可能。

第一種可能是接下來的字符相同，那麼這個子串的最長相同前後綴的長度就是 n+1。

然後寫到 next 數組即可，這很好理解。

但是如果下一個位置的字符不相等該怎麼辦呢？

注意接下來是整個算法最核心的，也是最具技巧的地方。

如果接下來的兩個字符不相等，那麼前面的這部分絕無可能形成最長前後綴。

因此我們只能找一個更短的。

如果能找到一個更短的，這就意味着這兩部分會形成一個共同前後綴。

然後我們繼續比較下一個字符就可以了，這就回到最初的問題。

那麼這兩部分相同意味着什麼呢？

不要忘了紅色部分是我們之前找到一個共同前後綴，也就是說紅色部分的子串完全相同。

而現在這兩個子串也相同，這就意味着這兩個更小的子串其實是紅色部分子串的最長前後綴。

不要忘了，此時我們的指針已經來到了這裏，前面這部分的 next 數組已經計算出來了。

通過查 next 數組，我們可以快速得到更短前後綴的長度。

既然紅色部分的長度是 n，那麼更短前後綴的長度其實就是 next[n-1]。

再來看下，紅色部分的長度是 n，那麼更短前後綴的長度是 next[n-1]。

也就是這個位置。

這就是計算 next 數組源代碼中 n=next[n-1] 這句話的含義。

現在我們再來看一遍整個過程。

此時兩個字符的長度不等，那麼我們只需要簡單查一下 next[n-1]：

這就是更短的前後綴長度，假設是 4。

此時前一個指針回退到位置 4，繼續比較下一個字符即可。

如果下一個字符相同，那麼當前位置 next 數組的值就是 n+1。

而如果下一個字符不相同，我們繼續查找 next[n-1]，然後前一個指針回退，繼續比較下一個位置即可。

這就是完整的 kmp 算法實現，可以看到整個代碼實際上只有 30 多行。

如果你能在 50 多年前寫出這幾行代碼，你也能和它們並列，在計算機科學史上會留下你的一筆。

好啦，以上就是本期全部內容。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/6knLuNCRshz9a8FRDATs4w