通俗易懂的講解KMP算法(字符串匹配算法)及代碼實現

一、本文簡介

本文的目的是簡單明了的講解KMP算法的思想及實現過程。

網上的文章的確有些雜亂，有的過淺，有的太深，希望本文對初學者是非常友好的。

其實KMP算法有一些改良版，這些是在理解KMP核心思想后的優化。

所以本文重點是講解KMP算法的核心，文章最后會有涉及一些改良過程。

二、KMP算法簡介

KMP算法是字符串匹配算法的一種。它以三個發明者命名，Knuth-Morris-Pratt，起頭的那個K就是著名科學家Donald Knuth。

三、KMP算法行走過程

首先我們先定義兩個字符串作為示例，被匹配串 S = "abcabdabcabeab"，匹配串 T = "abcabeab"。

我們的目標就是確定S中是否包含T。

KMP算法的核心是分析匹配串 T 的特征，看看匹配串 T 能告訴我們什么信息。我把 T 著色，如下

T = "abcabeab"

現在看起來似乎比較明顯了，三個著色點都是重復的 "ab"，似乎這個 T 能告訴我們它有重復的子串"ab"可以利用。那么它們到底怎么用？先不講具體怎么用，先走一遍KMP這個過程，但是大家需要留意這個"ab"。

1.

我們發現T在匹配成功 "abcab" 后到"e"時和S子串的"d"匹配不成功了。

這個時候我們可以得到的先驗就是目前T匹配過的S子串，就是"abcab"。而T本身就是"ab"重復的。所以"abcab"可以直接跳到第二個重復"ab"的位置，因為"abcab"中其它字符串開頭不可能產生和T對應的匹配，這是很直觀的。

因此T應該直接后移三個位置，并且用第三位的"c"和S剛才不匹配的"d"進行比較。

可以發現，S匹配的過程是不會回退的。因此匹配過程是S從頭到尾的一遍掃描(中間可能因為匹配成功退出)，所以這個查找過程是O(N)的復雜度。

2.

此時的匹配串是 "ab"， 它告訴我們目前匹配的是"ab"。這個不像"abcab"出現了重復"ab"，所以我們知道包括S[5]的"d"之前的子串是垃圾串。因此跳過S[5]重新開始匹配T。

最后完成匹配，可見，這樣一次對S的掃描完成了對T的查找。

那么對于機器如何實現？第四節會分析。

四、KMP算法核心解析

對于上面的過程，我們抽離出來的話，問題的根本就是對T串重復情況的一個判定。不管S是什么串，只要對T的構造模式分析清楚就可以完成上述跳轉過程。

因此需要一個數組記錄這個T的 模式函數。

這里先給出這個T的模式函數

1.每個字母對應模式函數的值就是匹配到當前位置 i 后，下一次T開始進行比較的下標。

2.而S的移動長度為 i - F(i-1)。

對應上面兩個問題

1.比如上面的匹配到的 "abcab" ，是T匹配到 T[5] 即"e"的時候出錯的。那么我們需要查看上一個字符的模式函數值，因為上一個函數值才代表了已經匹配的串。

發現F(4)=2，說明下次比較從T[2]即"c"開始。因為"abcab"有重復"ab"，第一個"ab"不需要比較。

2.而S下標移動多少呢？S下標的移動即找到T的初試位置對應的S的下標。對應上面第二張圖，S[3]和T的移動對應起來了。3的獲得就是通過上面公式 5-F(4)得到的。其實這個結果和1得到匹配位置的思路是一樣的，不過又向前移動對齊了開頭。

為什么如此構造這個模式函數？

就是因為F值表示了對于位置 i， T[i]有無重復，并且重復下標的位置在哪(F[i])。既然我們獲取了重復下標的位置，那么其它的相關值可以推出來了。

基于這個思路，再給出另外兩個T串的模式函數值，幫助大家思考。

1.

2.

如何快速構造這個模式函數？

這個留給大家思考一下了，應該也比較直接了，注意是查找重復位置。如果不大明白，可以參考下面的代碼。

五、KMP算法實現

 再添加個例子幫助大家思考：

S1 = "aaaaaaaaaaaaaaaab"  S2 = "aaaaafaaaaaaaaab"   T = "aaaab"

對于S1和S2兩種情況，應如何匹配。

代碼如下：

/*
    return val means the begin pos of haystack
    -1 means no matching substring
*/
int KMP(char *haystack, char *needle) {
    // pre-process
    if(haystack[0] == 0 && needle[0] == 0)
        return 0;

    int i, j, k, min, cur;

    //construct F(t) in vector len
    vector<int > len;
    len.push_back(0);
    for(i=1; needle[i] != 0; i++){
        if(len[i-1] == 0){
            if(needle[i] == needle[0])
                len.push_back(1);
            else
                len.push_back(0);
        }else{
            if(needle[i] == needle[len[i-1]])
                len.push_back(len[i-1]+1);
            else
                len.push_back(0);
        }
    }
    // KMP finder
    j = 0;
    for(i=0; haystack[i] != 0; ) {
        // matching
        for(; needle[j] != 0; j++) {
            if(haystack[i+j] != needle[j])
                break;
        }
        //finded
        if(needle[j] == 0)
            return i;
        else{ // jump
            if(j){
                cur = j - len[j-1];
                i += cur;
                j = len[j-1];
            }else{
                j = 0;
                i++;
            }
        }
    }
    //match failed
    return -1;
}

六、KMP算法改進

KMP算法有一些改進版本加速查找，一般可以通過S串中的一些信息加速匹配過程。

比如若  S = "aaaaaaaafaaaaaaaaaaaab", T = "aaaaaaab"。

在查找過程中，S中間的 "f" 起到了阻擋作用。但是由于我們只是考慮T的先驗信息，遇到"f" 不匹配會導致T每次后移一步進行新的匹配，直到T的開頭碰到了"f"。

但是如果我們加入"f"這個原串S的信息，由于"f" ！= "b" && "f" != "a" && i-1 = F(i-1) ，所以直接跳到"f"后進行新的匹配會更快速的查找。

但是這些改進都是基于KMP基礎算法之上的，因此把握核心要點不僅省時省力，更能有效擴展。

七、參考

[1] 《字符串匹配的KMP算法》 http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

[2] 算法導論