通俗理解 KMP 字元串匹配演算法

04-13

KMP 演算法是一個高效的字元串匹配演算法，由Knuth、Morris、Pratt三人提出，並使用三人名字的首字母命名。在KMP之前，字元串匹配演算法往往是遍歷字元串的每一個字元進行比對，演算法複雜度是O(mn)。而KMP演算法通過預處理能夠把複雜度降低到O(m+n)。

KMP演算法

假設給定一個字元串 1 ABCABCABDEF，現在需要搜索字元串 2 ABCABD 在字元串 1 中出現的位置。從 0 位置開始比對，到位置 5 時發現字元不相同，字元串 1 的字元為 C，字元串 2 的字元為 D。接下來如何繼續比對呢？KMP 演算法的核心就在於這裡。考慮到字元串 2 中有兩個 AB 重複出現，因此可以把第一個 AB 移動到第二個 AB 處繼續比對。這個移動過程就是利用了已經匹配的字元信息，直接將字元串前移 3 位提高了比對效率。

假設給定一個長度為 n 的字元串 O ，查找長度為 m 的字元串 f 在 O中出現的位置，如下圖所示(圖片來自網路)。

當比對到第 i 個字元不相等時，需要把字元串 f 向前移動繼續比對，KMP演算法通過計算最大公共長度來移動。當滿足如下條件時，f 可以前移 k 位繼續比對。

字元串 A 是 f 的一個前綴；
字元串 B 是 f 的一個後綴；
字元串 A 和字元串 B 相等。

KMP 演算法的核心即在於求解 f 中每一個位置之前的字元串的前綴和後綴的最大公共長度。注意，這個最大長度不包括字元串本身。當比較到第 i 位置時，如果不相同，而此時最大公共長度為 j，則 f 前移的距離為 k = i – j 。

最大公共長度的計算

前綴是除了最後一個字元的子字元串，後綴是指除了第一個字元的子字元串。對於字元串 ABCA，前綴有 A、AB、ABC，後綴有 A、CA、BCA，相同的前綴後綴只有 A。最大公共長度是指當前位置前面的字元串相同前綴後綴的最大長度，使用 next 數組表示。根據這個規則，前面的字元串 2 ABCABD 的 next 數組如下表格所示。對於長度為 m 的字元串，next 數組的長度為 m + 1。顯而易見，next[0] = next[1] = 0。

已知 A3 = A0，next[4] = 1，計算 next[5] 時只需要比對 B4 = B1 則 A3B4 = A0B1，next[5] = next[4] + 1 = 2。

已知 A3B4 = A0B1，next[5] = 2，計算 next[6] 時首先比較 D5 ≠ C2 則 A3B4D5 ≠ A0B1C2。如果存在一個以 B 結尾的公共前綴，那麼這個前綴一定在 C2 的前面，這個前綴的長度為 next[next[5]] = 0，因此 C2 的前面沒有這樣的前綴，並且 D5 ≠ A0，next[6] = 0。

假設我們現在已經求得 next[1]、next[2]、……、next[i]，現在要求next[i+1]。可以看出，如果位置 i 和位置 next[i] 處的兩個字元相同，則 next[i+1] = next[i] + 1；如果兩個位置的字元不相同，可以繼續向前搜索，獲得其最大公共長度 next[next[i]]，然後再和位置 i 的字元比較，直到能最終確定結果。（圖片來自網路）

根據上面的分析，不難寫出求解 next 數組的代碼如下。

public static int[] getNext(String find){ int[] next = new int[find.length() + 1]; //0 和 1 的值肯定是 0 next[0] = 0; next[1] = 0; //根據 next[i] 推算 next[i+1] for(int i = 1; i < find.length(); i ++){ int j = next[i]; //比較 i 位置與 j 位置的字元 //如果不等，則 j 取 next[j] while (j > 0 && (find.charAt(i) != find.charAt(j))){ j = next[j]; } //如果相等，則 j 加一即可 if(find.charAt(i) == find.charAt(j)){ j ++; } next[i+1] = j; } return next;}

字元串匹配

字元串匹配的過程和求解 next 數組的過程類似。假設搜索字元串 f 在字元串 O 中出現的位置，f 的下標為 j，O 的下標為 i。如果 O(i) = f(j)，則 j = j + 1，繼續比較 f 中的下一個字元；如果 O(i) ≠ f(j)，則 j = next[j]，繼續比較 f 中位置為 next[j] 的字元，相當於 f 前移了 i - j 位。當 f 的下標 j 移動到末尾時，說明匹配成功，此時可以算出第一次出現的位置是 i - j。

如下圖所示，假設 O 為 ABCABCABDEF，f 為 ABCABD。O(4) = f(4)，下一步繼續比對 O(5) 和 f(5) 即可；O(5) ≠ f(5)，則 f 的下一個比對字元位置為 next[5] = 2，下一步繼續比對 O(5) 和 f(2)，相當於 f 前移了 5 - 2 = 3 位。當比對到 O(8) = f(5) 時，f 已經比對到末尾，匹配成功，此時算出 O 中出現的位置為 8 - 5 = 3。

根據上面的分析，不難寫出匹配字元串的代碼如下。

public static List<Integer> indexOf(String text,String find){ int[] next = getNext(find); List<Integer> index = new LinkedList<>(); //i 表示 text 中的位置，j 表示 find 中的位置 int j = 0; //遍歷 text 中的字元 for(int i = 0; i < text.length(); i ++){ //這裡是 KMP 演算法的關鍵點，移動位置為 next[j] while (j > 0 && (text.charAt(i) != find.charAt(j))){ j = next[j]; } //如果 i 位置和 j 位置的字元相同，移動一位 if(text.charAt(i) == find.charAt(j)){ j ++; } //如果 j 已經到了 find 的尾部，表示已經找到 if(j == find.length()) { // i - j + 1 即為 find 在 text 中出現的位置 index.add(i - j + 1); //這裡是 KMP 演算法的關鍵點，移動位置為 next[j] j = next[j]; } } return index;}