如何更好的理解和掌握 KMP 演算法?

如何更好的理解和掌握 KMP 演算法

---

甲：abbaabbaaba

在裡面尋找

乙：abbaaba

發現第 7 個字元不匹配。

這時候甲把乙叫走了，說你先一邊玩去，我自己研究下。

然後甲想，自己已經知道乙的前 6 個字元就是自己的前 6 個字元，不妨先「自己與自己匹配一番」，即用 abbaab 去匹配 abbaab。

向右錯 1 個位，發現第一個就不一樣（不匹配）；向右錯 2 個位，還是不匹配。

當錯 3 個位的時候，甲發現匹配了一個 a，但是第二個 b 不匹配。

當錯 4 個位的時候，匹配了兩個，錯 5 個位不匹配。後面的東西甲就不知道了，因為他只知道前 6 個字元。

隨後，甲把乙叫了過來：

「我已經知道你下一次匹配開始的位置了，來，讓你的頭部對齊我的第 5 個字元，然後從你的第 3 個字元開始繼續匹配我吧！」

關鍵的地方，在於不要讓乙「前功盡棄」——已經匹配了 6 個了，還差一個就結束了，這時不匹配導致從 0 開始，多可惜啊！

現在我告訴你，在不匹配的情況下，你仍然已經匹配了 2 個（乙內心：還好不是 0），並且你可以繼續從不匹配的地方開始比較，即用你的第 3 個字元與我繼續匹配。

那，這個 2 你是怎麼算的？

我在你來之前就算好啦！

我先與自己進行匹配（預處理），對每個子字元串 [0...i]，找其「相匹配的前綴與後綴中，最長的那個字元串的長度」。

UCCU，從你的第 6 個字元往左看，恰好 [ab] 與你的前綴 [ab] 匹配，但是我的第 7 個字元並不知道你的第 3 個字元是否與我一樣，所以你直接從這裡開始繼續匹配我。

---

以上為 KMP 的基本思想，關鍵在於如何高效地預處理，這裡有個很好的例子：abababzabababa。

讓我們來列個表計算一下：

子字元串 a b a b a b z a b a b a b a
最大匹配數 0 0 1 2 3 4 0 1 2 3 4 5 6 ?


一直算到 6 都很容易。在往下算之前，先回顧下我們所做的工作：子字元串 abababzababab 前綴後綴最大匹配了 6 個（ababab），那次大匹配了多少呢？

容易看出次大匹配了 4 個（abab），更仔細地觀察可以發現，次大匹配的前綴後綴只可能在 ababab 中，直接查上表可以得出該值為 4。

第三大的匹配同理，它既然比 4 要小，那前綴後綴也只能在 abab 中找，查表可得該值為 2。

再往下就沒有更小的匹配了。

回顧完畢，來計算 ? 的值：既然末尾字母不是 z，那麼就不能直接 +1 了，我們可以用次大匹配來看，即 abab 之後的 a，剛好它與末尾的 a 匹配，所以 ? 值為 5。

---

上 Java 代碼，它已經呼之欲出了：

int[] calc_max_match_lengths(String pattern) {
int[] max_match_lengths = new int[pattern.length()];
int max_length = 0;
for (int i = 1; i &< pattern.length(); i++) { while (max_length &> 0 pattern.charAt(max_length) != pattern.charAt(i)) {
max_length = max_match_lengths[max_length - 1]; // ①
}
if (pattern.charAt(i) == pattern.charAt(max_length)) {
max_length++; // ②
}
max_match_lengths[i] = max_length;
}
return max_match_lengths;
}


有了代碼後，容易證明它的複雜度是線性的（即運算時間與 pattern 的長度是線性關係）：由 ② 可以看出 max_length 在整個循環中最多增加 pattern.length() - 1 次，所以讓 max_length 減少的 ① 在整個 for 循環中最多會執行 pattern.length() - 1 次，從而 calc_max_match_lengths 的複雜度是線性的。

KMP 匹配的思想和求最大匹配數的過程類似，從 count 值的增減容易看出它也是線性複雜度的：

// 在 text 中尋找 pattern，返回所有匹配的位置開頭
List& search(String text, String pattern) {
List& positions = new ArrayList&<&>();
int[] max_match_lengths = calc_max_match_lengths(pattern);
int count = 0;
for (int i = 0; i &< text.length(); i++) { while (count &> 0 pattern.charAt(count) != text.charAt(i)) {
count = max_match_lengths[count - 1];
}
if (pattern.charAt(count) == text.charAt(i)) {
count++;
}
if (count == pattern.length()) {
positions.add(i - pattern.length() + 1);
count = max_match_lengths[count - 1];
}
}
return positions;
}


以上。

---

KMP實際上是AC自動機的退化版本，即模式串個數為1的情況。我之前KMP理解起來也很困難，但是後來學了AC自動機就很容易理解了。

看起來AC自動機比KMP高端，實際上可以看做一個有條件轉移的圖。匹配就是從起點沿著邊按條件進行轉移，理解起來比KMP要容易。

---

有些演算法，適合從它產生的動機，如何設計與解決問題這樣正向地去介紹。但KMP演算法真的不適合這樣去學。最好的辦法是先搞清楚它所用的數據結構是什麼，再搞清楚怎麼用，最後為什麼的問題就會有恍然大悟的感覺。我試著從這個思路再介紹一下。大家只需要記住一點，PMT是什麼東西。然後自己臨時推這個演算法也是能推出來的，完全不需要死記硬背。

KMP演算法的核心，是一個被稱為部分匹配表(Partial Match Table)的數組。我覺得理解KMP的最大障礙就是很多人在看了很多關於KMP的文章之後，仍然搞不懂PMT中的值代表了什麼意思。這裡我們拋開所有的枝枝蔓蔓，先來解釋一下這個數據到底是什麼。

對於字元串「abababca」，它的PMT如下表所示：

就像例子中所示的，如果待匹配的模式字元串有8個字元，那麼PMT就會有8個值。

我先解釋一下字元串的前綴和後綴。如果字元串A和B，存在A=BS，其中S是任意的非空字元串，那就稱B為A的前綴。例如，」Harry」的前綴包括{」H」, 」Ha」, 」Har」, 」Harr」}，我們把所有前綴組成的集合，稱為字元串的前綴集合。同樣可以定義後綴A=SB， 其中S是任意的非空字元串，那就稱B為A的後綴，例如，」Potter」的後綴包括{」otter」, 」tter」, 」ter」, 」er」, 」r」}，然後把所有後綴組成的集合，稱為字元串的後綴集合。要注意的是，字元串本身並不是自己的後綴。

有了這個定義，就可以說明PMT中的值的意義了。PMT中的值是字元串的前綴集合與後綴集合的交集中最長元素的長度。例如，對於」aba」，它的前綴集合為{」a」, 」ab」}，後綴 集合為{」ba」, 」a」}。兩個集合的交集為{」a」}，那麼長度最長的元素就是字元串」a」了，長 度為1，所以對於」aba」而言，它在PMT表中對應的值就是1。再比如，對於字元串」ababa」，它的前綴集合為{」a」, 」ab」, 」aba」, 」abab」}，它的後綴集合為{」baba」, 」aba」, 」ba」, 」a」}， 兩個集合的交集為{」a」, 」aba」}，其中最長的元素為」aba」，長度為3。

好了，解釋清楚這個表是什麼之後，我們再來看如何使用這個表來加速字元串的查找，以及這樣用的道理是什麼。如圖 1.12 所示，要在主字元串"ababababca"中查找模式字元串"abababca"。如果在 j 處字元不匹配，那麼由於前邊所說的模式字元串 PMT 的性質，主字元串中 i 指針之前的 PMT[j ?1] 位就一定與模式字元串的第 0 位至第 PMT[j?1] 位是相同的。這是因為主字元串在 i 位失配，也就意味著主字元串從 i?j 到 i 這一段是與模式字元串的 0 到 j 這一段是完全相同的。而我們上面也解釋了，模式字元串從 0 到 j?1 ，在這個例子中就是」ababab」，其前綴集合與後綴集合的交集的最長元素為」abab」， 長度為4。所以就可以斷言，主字元串中i指針之前的 4 位一定與模式字元串的第0位至第 4 位是相同的，即長度為 4 的後綴與前綴相同。這樣一來，我們就可以將這些字元段的比較省略掉。具體的做法是，保持i指針不動，然後將j指針指向模式字元串的PMT[j ?1]位即可。

簡言之，以圖中的例子來說，在 i 處失配，那麼主字元串和模式字元串的前邊6位就是相同的。又因為模式字元串的前6位，它的前4位前綴和後4位後綴是相同的，所以我們推知主字元串i之前的4位和模式字元串開頭的4位是相同的。就是圖中的灰色部分。那這部分就不用再比較了。

有了上面的思路，我們就可以使用PMT加速字元串的查找了。我們看到如果是在 j 位 失配，那麼影響 j 指針回溯的位置的其實是第 j ?1 位的 PMT 值，所以為了編程的方便， 我們不直接使用PMT數組，而是將PMT數組向後偏移一位。我們把新得到的這個數組稱為next數組。下面給出根據next數組進行字元串匹配加速的字元串匹配程序。其中要注意的一個技巧是，在把PMT進行向右偏移時，第0位的值，我們將其設成了-1，這只是為了編程的方便，並沒有其他的意義。在本節的例子中，next數組如下表所示。

具體的程序如下所示：

int KMP(char * t, char * p)
{
int i = 0;
int j = 0;

while (i &< strlen(t) j &< strlen(p)) { if (j == -1 || t[i] == p[j]) { i++; j++; } else j = next[j]; } if (j == strlen(p)) return i - j; else return -1; }

好了，講到這裡，其實KMP演算法的主體就已經講解完了。你會發現，其實KMP演算法的動機是很簡單的，解決的方案也很簡單。遠沒有很多教材和演算法書里所講的那麼亂七八糟，只要搞明白了PMT的意義，其實整個演算法都迎刃而解。

現在，我們再看一下如何編程快速求得next數組。其實，求next數組的過程完全可以看成字元串匹配的過程，即以模式字元串為主字元串，以模式字元串的前綴為目標字元串，一旦字元串匹配成功，那麼當前的next值就是匹配成功的字元串的長度。

具體來說，就是從模式字元串的第一位(注意，不包括第0位)開始對自身進行匹配運算。 在任一位置，能匹配的最長長度就是當前位置的next值。如下圖所示。

求next數組值的程序如下所示：

void getNext(char * p, int * next)
{
next[0] = -1;
int i = 0, j = -1;

while (i &< strlen(p)) { if (j == -1 || p[i] == p[j]) { ++i; ++j; next[i] = j; } else j = next[j]; } }

至此，KMP演算法就全部介紹完了。94贊0評論慘案。。。發生了什麼⊙?⊙？

更多編程相關的內容，請關注我的公眾號：

我的公眾號

---

一點直觀的理解：

在模式串P的匹配過程中，假如在某個位置失配了，我們希望能不回溯從頭匹配，因為在之前的匹配過程中已經積累了足夠的信息，於是問題完全變成了在每個位置計算模式串後綴和前綴的最長匹配，一個簡單的動態規劃。

---

為什麼要執著於 KMP 呢？

glibc 2.9 之後的 strstr() 在一定情況下會用高效的 Two Way algorithm，之前的版本是普通的二重循環查找，因此用不著自己寫。

而且 glibc 的作者一度也寫錯過，https://sourceware.org/bugzilla/show_bug.cgi?id=12092

ps. strstr() 還不止一次出過 bug：https://sourceware.org/bugzilla/show_bug.cgi?id=12100https://sourceware.org/bugzilla/show_bug.cgi?id=14602 等等。

c - What is the fastest substring search algorithm?

---

同覺得沒必要糾結於KMP演算法，這裡推薦另外一個有趣的演算法，叫Rabin-Karp演算法，理解起來相對容易。

假設有一個大的字元串t,長度為n,和一個要匹配的字元串s，長度為m，n&>&>m。

Rabin-Karp演算法的想法是為t每一個長度為m的子串求一個hash值，然後和s的hash值匹配， 如果匹配上了，再去匹配字元串本身。

正常情況下計算hash值的複雜度是o(m)， 所以整個演算法依然是o(mn)。但是如果設計較好的hash演算法， 讓每個子串的hash值通過它前一個子串的hash值快速算出來（因為他們畢竟有m-1個字元完全一樣）， 這樣平均複雜度就能降低到o(n)。

一個最簡單的hash函數即m個元素的和。在已知前一個字元串的hash值以及兩個字元串的差異之後，可以快速求出後一個字元串的hash值。

---

KMP演算法詳解 by Matrix67

http://www.matrix67.com/blog/archives/115

自己推導一下。然後找兩個OnlineJudge上的題目用一下。

---

廣告一下，可以看我的這篇博客

（原創）詳解KMP演算法

---

學習有限狀態自動機和正則表達式原理你就明白。

---

當你的水平足以理解後綴數組的時候。

---

從有限狀態自動機的角度理解KMP演算法 - 水牛

用圖來理解更直觀。

---

渣渣也來答一發，首先為什麼要使用KMP,比如abc這個串找它在abababbcabcac這個串中第一次出現的位置，那麼如果直接暴力雙重循環的話，abc的c不匹配母串中的第三個字母a後，abc將開始從母串中的頭位置的下一個位置開始尋找，就是abc開始匹配母串中第二個字母bab...這樣，

而KMP的優勢就在於可以讓模式串向右滑動儘可能多的距離

就是abc直接從模式串的第三個字母aba...開始匹配，為了實現這一目標，KMP需要預處理出模式串的next數組

理解KMP的關鍵是你要理解next數組，next數組中保存的就是一個模式串的後綴與前綴的最長匹配，即next[i]=max(len),使得next[0]=next[i-len],next[1]=next[i-len+1]...,next[len-1]=next[i-1],比如aaabcaaa這麼一個串，那麼它的next數組的值應該依次為

next[0]=-1,next[1]=0,next[2]=1,next[3]=2,next[4]=0,next[5]=0,next[6]=1,next[7]=2,next[8]=3.

void get_next(char *T,int *next,int len)
{
int j=0,k=-1;
next[0]=-1;
while(j&<=len) { if(k==-1||T[j]==T[k]) { j++;k++; next[j]=k; } else k=next[k]; } }

插段獲取next數組的代碼題主自己體會一下，其實就是模式串自己和自己匹配一次，然後是兩個字元串匹配的代碼

int KMP(char *A,char *B,int len,int len2)
{
int *next=new int[len+5];
get_next(B,next,len);
int i=0,j=0,ans=0;
while(i&

還是以之前的abababbcabcac為例，i=2,j=2時就不匹配了，這時next[2]=0，j=next[2]=0,相當於將模式串向右拉動2格

其實不難辣。。。題主自己手推一下就領悟了

---

我覺得bm更加優秀

---

把KMP代碼看懂不就完了嗎？

---

July有一篇專門講KMP的文章。推薦看看。

從頭到尾徹底理解KMP http://blog.csdn.net/v_july_v/article/details/7041827

---

掌握這句話，f[i]是到i為止最長的既是前綴也是後綴的串的長度。代碼按照這個定義來推。然後就理解next[i]怎麼算就是模式串自己的前綴和自己後綴匹配。再理解和另一個字元串j匹配過程中匹配到pattern[i] 和org[j]不同之後， 把模式串向後拉，讓到這裡的後綴相同的前綴不用再算一遍。這就是最基本的KMP。

---

建議先學AC自動機，雖然AC自動機聽起來高端，但是好理解多了，AC自動機會了，KMP也就會了

---

KMP演算法目的：主字元串上匹配過的位置不在重複，節省時間。

當主字元串和子字元串在 i 位置發生匹配錯誤的時候，可以把接下來要匹配的情況分成兩類，1）子字元串頭部移動到匹配錯誤發生的位置 i，重新開始；2）子字元串頭部每次向後移動一位，進行匹配。

很顯然如果2）不成功，接下來考慮的就是1）的情況（想像字字元串是從左往右移動，和主字元串匹配的）。有沒有一個簡單的、不需要子字元串遍歷所有 i 以前的位置就能確定是否和主字元串匹配的辦法呢？(也就是2）該怎麼判斷) 有的：

2）的成功必須滿足兩個條件：（1）串1 == 串2； （2）主字元串 i 位置能與子字元串匹配。

（2）中與主字元串 i 位置匹配的是子字元串中的哪個位置，這由（1）決定：子字元串中的串2的後一位就是。

於是全剩下解決（1）了。這個問題可以轉換成子字元串自己和自己比較，為什麼呢？因為我們知道串1對應了子字元串中和主字元串匹配上的最長序列的尾巴，這是從前一次匹配中得到的結論：

於是所有問題就變成了子字元串存不存在前綴（串2）和後綴（對應串1）相等的問題了。

---

看我的文章：KMP演算法 - 劉毅

---

去讀sedgewick的algorithms。然後自己寫一遍就全明白了。

---

推薦閱讀：