KMP演算法 理解與實現
KMP演算法，背景不必多說，主要想寫一寫自己對KMP演算法的一些理解和其具體實現。
關於KMP演算法的原理，阮一峰老師的這篇文章足矣。
ofollow,noindex">字串匹配的KMP演算法
文中對KMP演算法的匹配過程以及“部分匹配表”具體代表什麼，都解釋的十分簡潔明瞭，看過之後也算是對KMP演算法有了一個直觀的瞭解。
下面我想就演算法的具體實現，尤其是“部分匹配表”的生成（個人認為KMP演算法實現中，最不容易理解的部分），進行一些分析。
KMP演算法具體實現
KMP演算法的主體是，在失去匹配時，查詢最後一個匹配字元所對應的“部分匹配表“中的值，然後向前移動，移動位數為：
移動位數 = 已匹配的字元數 - 對應的部分匹配值
比如對如下的匹配：
在 D 處失去匹配，那麼查詢最後一個匹配字元 B 在部分匹配表中的值為 2 。
則向前移動6-2= 4 位。（其實就相當於從搜尋詞的第二位開始重新進行比較）
下面是演算法主體的實現
這裡的 next 陣列即“部分匹配表”。注意因為搜尋詞最後一位對應的部分匹配值是沒有意義的，所以為了程式設計方便，我們將”部分匹配表“整體向後移一位，並把第一位設為-1。
//Java /** * KMP演算法.<br/> * 在目標字串中對搜尋詞進行搜尋。<br/> * * @param t 目標字串 * @param p 搜搜詞 * @return 搜尋詞第一次匹配到的起始位置或-1 */ public int KMP(String t, String p) { char[] target = t.toCharArray(); char[] pattern = p.toCharArray(); // 目標字串下標 int i = 0; // 搜尋詞下標 int j = 0; // 整體右移一位的部分匹配表 int[] next = getNext(pattern); while (i < target.length && j < patter.length) { // j == -1 表示從搜尋詞最開始進行匹配 if (j == -1 || target[i] == pattern[j]) { i++; j++; // 匹配失敗時，查詢“部分匹配表”，得到搜尋詞位置j以前的最大共同前後綴長度 // 將j移動到最大共同前後綴長度的後一位，然後再繼續進行匹配 } else { j = next[j]; } } // 搜尋詞每一位都能匹配成功，返回匹配的的起始位置 if (j == pattern.length) return i - j; else return -1; }
KMP演算法的搜尋過程還是比較好理解的。
接下來最容易被繞進去的部分來了，求解“部分匹配表”即 next 陣列。
部分匹配表(next陣列)的生成
其實，求next陣列的過程完全可以看成字串匹配的過程，即以搜尋詞為主字串，以搜尋詞的 字首 為目標字串，一旦字串匹配成功，那麼當前的next值就是匹配成功的字串的長度。
具體來說，就是從模式字串的第一位( 注意，不包括第0位 )開始對自身進行匹配運算。 在任一位置，能匹配的最長長度就是當前位置的next值，如下圖所示。
(這裡next陣列下標從1開始表示)
下面是演算法的具體實現
//Java
/**
* 生成部分匹配表.<br/>
* 生成搜尋詞的部分匹配表<br/>
*
* @param p 搜搜詞
* @return 部分匹配表
*/
private int[] getNext(String pattern) {
char[] p = pattern.toCharArray();
int[] next = new int[p.length];
// 第一位設為-1，方便判斷當前位置是否為搜尋詞的最開始
next[0] = -1;
int i = 0;
int j = -1;
while(i < p.length - 1) {
if (j == -1 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
這裡 j = next[j] 的寫法十分巧妙，卻有點難以理解(至少我一開始想了很久...)，其實就是一個不斷的回溯過程。
next[j] 表示 p[j] 前面的 最大 共通字首字尾的 長度 ，那麼 p[next[j]] 則表示這個共通前後綴的最後一個字元。
如果 p[next[j]] == p[j] 則可以肯定 next[j+1] == next[j] + 1 。而當 p[next[j]] != p[j] 時，就應該考慮，既然 next[j] 長度的字首字尾都不能匹配了，那麼就應該縮短這個匹配的長度。直接從頭開始重新匹配，那就是最樸素的暴力匹配了，效率太低。
此時對於 next[j] 這個字串本身，也是有自己的最大共通前後綴的，那麼 next[next[j]] 則代表 p[next[j]] 前面的 最大 共通字首字尾長度。所以令 j = next[j] 然後從 p[j] 重新開始比較，如果不匹配的話再重複以上過程，最終得到結果。