我理解的 KMP 算法

最近一段時間，我一直在看 KMP 字符串模式匹配算法的各種不同解釋。因為各種原因，沒有 找到 一種我覺得好的解釋。當我讀到“ …… 的前綴的后綴的 前綴”時，我會不停地拍自己的腦袋 。

最后，花了大約30分鐘將《算法 導論》里相同的部分反反復復讀了以后，我決定坐下來做一些例子和圖解。現在，我已經搞清楚了這個算法并能對它解釋。對于那些和我有一樣想法的人，下面是我自己的理解。一方面，我不打算解釋為什么它比樸素的字符串匹配效率更高；這些在很多地方都已經解釋得非常好了。我要說明的是，它究竟是如何工作的。

部分匹配表

毫無疑問，KMP算法的精髓是 部分匹配表。我理解KMP算法時，最大的障礙就在于是否充分明白部分匹配表里的值所代表的意義。下面我會盡可能簡單地來解釋這些。

下面這個是 “a bababca”這個模板的部分匹配表：

如果我有一個8個字符的模板（這里我們 就用“abababca”來舉例子），我的部分匹配表將會有8格。如果此時此刻我正匹配模板的第8格即最后一格，那意味著我匹配了整個模板（“abababca”）；如果我正匹配模板的第7格，則意味著當前僅匹配了整個模板的前7位（“abababc”），此時第8位(“a”)是無關的，不用去管它；如果我此時此刻正匹配模板的第6格，那意味著……看到這里你應該已經明白我的意思了。目前我還沒有提到部分匹配表每格數據的含義，在這里僅僅是交代了大概。

現在，為了說明剛剛提到的每格數據的含義，我們首先要明白什么是 最優前綴 什么是 最優后綴 。

最優前綴：一個字符串中 ， 去除一個或多個尾部 的字符所得的新字符串就是最優前綴。例如 “S”、 “Sn”、 “Sna”、 “Snap”都是“Snape”的最優前綴。

最優后綴：一個字符串中，去除一個或多個首部的字符所得的新字符串就是最優后綴。例如“agrid”、 “grid”、“rid”、 “id”、“d”都是 “Hagrid”的最優后綴。

有了兩個概念，我現在可以用一句話來概括部分匹配表里每列數據的含義了：

模板（子模板）中，既是最優前綴也是最優后綴的最長字符串的長度。

下面我舉例說明一下這句話。我們來看部分匹配表的第3格數據，如果你還記得我在前面提到的，這 意味著我們目前僅僅關心前3個字母（“aba”）。在“aba”這個子模板中，有兩個最優前綴（“a”和“ab”）和兩個最優后綴（“a”和“ba”）。其中，最優前綴“ab”并不是最優后綴。因此，最優前綴與最優后綴中，相同的只有“a”。那么，此時此刻 既是最優前綴也是最優后綴的最長字符串的長度 就是1了。

我們再來試試 第4格，我們應該是關注于前4個字母（“abab”）。可以看出，有3個最優前綴（“a”、“ab”、 “aba”）和3個最優后綴（“b”、“ab”、“bab”）。這一次 “ab” 既是最優前綴也是最優后綴，并且長度為2，因此，部分匹配表的第4格值為2。

這是很有趣的例子，我們再看看第5格的情況，也就是考慮“ababa”。我們有4個最優前綴（“a”、 “ab”、“aba”，和 “abab”）和4個最優后綴（“a”、 “ba”、“aba”，和“baba”）。現在，有兩個匹配“a”和“aba” 既是最優前綴也是最優后綴，而“aba”比“a”要長，所以部分匹配表的第5格值為3。

跳過中間的直接來看 第7格，此時只考慮字母“abababc”。即使不一一枚舉出所有的最優前綴與最優后綴也不難看出，這兩個集合之間不會有任何的交集。因為，所有最優后 綴都以“c”結尾，但沒有任何最優前綴是以“c”結尾的，所以沒有相匹配的，因此第7格值為0。

最后，讓我們看看第8格，也就是考慮整個模 板（abababca）。它的最優前綴與最有后綴都以“a”開頭以“a”結尾，所以第8列的值至少是1。然而1就是最終結果了，所有長度大于等于2的最優后綴都包含“c”，但只有“abababc”這一個最優前綴包含“c”，這個7位的最優后綴“bababca”并不匹配，所以第8列最終賦值為1。

如何使用部分匹配表

當我們找到了部分匹配的字符串時 ，可 以用部分匹配表里的值來跳過前面一些字符（而不是重復進行沒有必要的比較）。具體是這樣工作的：

如果已經匹配到的部分字符串的長度為partial_match_length且  table[partial_match_length] > 1， 那么我們可以跳過 partial_match_length- table[partial_match_length - 1] 個字符。

比如，我們拿“abababca”來這個模板來匹配文本“ bacbababaabcbab”的話，我們 的部分匹配表應該是這樣的：

char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

第一次匹配的時候是在這里

bacbababaabcbab
 |
 abababca

partial_match_length值為1，對應的 table[partial_match_length - 1] （即 table[0] ）值為 0。所以，這種情 況下我們不能跳過任何字符。下一次的匹配是這里：

bacbababaabcbab
    |||||
    abababca

partial_match_length值為5，對應的 table[partial_match_length - 1] （即 table[4] ）值為 3。這意 味著我們可以跳過  partial_match_length- table[partial_match_length - 1] （即 5 – table[4] 或 5 – 3 亦即 2 ）個字符：

// x 表示一個跳過 bacbababaabcbab
    xx|||
      abababca

partial_match_length值為3，對應的 table[partial_match_length - 1] （即 table[2] ）值為1，這意味著我們可以跳過  partial_match_length- table[partial_match_length - 1] （即 3- table[2] 或 3 – 1 亦即 2 ）個字符：

// x 表示一個跳過 bacbababaabcbab
      xx|
        abababca

現在，模板長度大于所剩余的目標字符串長度，所以我們知道不會再有匹配了。

結語

那么你應該搞明白了吧。就像我一開始說的，這篇文章沒有關于KMP多余的解釋或者或枯燥的證明；而是我自己 的理解，以及 我發現的容易讓人感到迷惑部分的詳盡解釋。如果你有任何疑問或者發現我這篇文章哪里寫錯了，請給我留言；也許我們都會有所收獲。