KMP是一種著名的字符串模式匹配算法，它的名稱來自三個發明人的名字。這個算法的一個特點就是，在匹配時，主串的指針不用回溯，整個匹配過程中，只需要對主串掃描一遍就可以了。因此適合對大字符串進行匹配。

搜了網上很多KMP的代碼下來調試，發現不是下標越界，就是死循環的，相當詭異...最后重新拿起嚴老師那本《數據結構》來翻，各種費解，有個地方用下標值和字符串下標0的元素做判斷，更是詭異了...

過了一天，忽然覺悟了。網上這些代碼都是來自《數據結構》或者和他同源的版本的，而它使用的是以下標1為起始的字符串！對這種字符串組織格式，下標0存放的是字符串的長度。

可是如今主流的語言，幾乎都是用的下標0作為起始，書本上的代碼顯然沒法用，那就自己重寫一個吧。

?

算法的原理

字符串匹配嘛，無非就是兩個指針，分別指向主串和模式串，然后依次往后移，檢查是否一致。在遇到不能匹配的情況時（簡稱“失配”），一般的方法，就是讓兩個指針回溯，主串指針往后再移動一位，從頭開始匹配。這其中做了很多重復勞動，我們可以分析一下：

可以看到模式串在匹配到下標5時失配了。
我們抓出模式串和主串在前方匹配的5個字符，并在模式串部分的前端和主串部分的后端找到了一對最長的相等的字串（不等于原來的串），用陰影標記一下，后面有用。

接著移動模式串，繼續匹配：

看出什么規律了么？每次比較，其實都是“abaab”的前端和后端的字串進行比較：
第一回是"abaa"vs"baab"
第二回是"aba"vs"aab"
第三回是"ab"vs"ab"
可見，只有在模式串部分的前端和主串部分的后端重合的時候，才可能繼續匹配。

是這樣么？當然是的，因為我們之前找出的是最長的，相等的字串！

這樣就能把中間無效的對比步驟省略，主串的指針不變，模式串的指針直接跳到下標2繼續匹配。這里的下標2就等于最長相等字串的長度。

接著推廣到更一般的情形：
假設主串s，模式串patten，s和patten分別在下標i，j處失配，

如果j>0，那么，
顯而易見，'s_i-k...s_i-1' = 'patten₀...patten_k-1'，此串長度為k，故下一步模式串指針應當跳轉到下標k繼續匹配。
在這里，因為's_i-k...s_i-1' =?'patten_j-k...patten_j-1'，得到'patten₀...patten_k-1' =?'patten_j-k...patten_j-1'，所以給定patten和j的情況下，k的值也是固定的。

如果j=0，那么i應當往后挪一位，j不變，重頭匹配

至此，對于給定的patten，可以得到一個j->k的映射關系，記為數組next，其中，k = next[j]：
next[j] = Max{ k | 0<=k<j 并且?'patten₀...patten_k-1' =?'patten_j-k...patten_j-1' }
當且僅當j == 0時，next[j] = -1（-1其實是沒有意義的，在這里為了計算方便）

?

依照這個定義，已經可以寫出一個計算next的弱弱的實現了。不過我先買個關子，先把主串的匹配搞定再說。

?

主串匹配算法

有了之前的分析，主串匹配的代碼基本就可以一蹴而就了（Java代碼）：

static int Kmp(String s, String patten) {int i = 0, j = -1;int[] next = GetNext(patten);// 待實現while (i < s.length() && j < patten.length()) {if (j == -1 || s.charAt(i) == patten.charAt(j)) {i++;j++;} else {j = next[j];// 失配時跳轉}}if (j == patten.length()) // 完全匹配return i - j;return -1; }

這兒有一處很巧妙地的地方：
next[0]是恒為-1的，所以如果在下標0處失配，則下一次循環j等于-1，i就會在循環中指向下一個字符，j也恢復為0。

?

模式串的next數組生成算法

看下面這張圖

假設模式串上的下標i，模式串下的下標j，那么
顯然next[5] = 2是由patten_i=4?= patten_j=1推出的，
推廣到一般的情況，也就是說當patten與自身錯位匹配時，當他們在i，j（i>j）處匹配時，
此時可以得到next[i+1] = j+1
如果j = 0時就失配了的話，自然next[i+1]應當等于0

至此，寫出代碼也就不難了，有些小技巧卻要注意一下（Java代碼）：

static int[] GetNext(String s) {int i = 0, j = -1;int[] next = new int[s.length()];next[0] = -1; // 這個初始化時必須的while( i<s.length()-1){if( j == -1 || s.charAt(i) == s.charAt(j)){i++;j++;next[i] = j;}else{j = next[j];// 當j在下標零處失配，代碼會怎么執行呢？}}return next; }

?

這個求next數組的方式和KMP算法的主體是不是很像呢？

總結

以上是生活随笔為你收集整理的每周一算法之六——KMP字符串匹配算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。