KMP 算法詳解
一、什麼是 KMP 算法
KMP 是一種字符串匹配算法。比如，一個字符串 ASDFASDFASD，我想知道其是否包含 ASDFS 這個子串，這個時候就用到了 KMP 算法啦。這時候可能有人就要問啦，不就是字符串匹配嘛，這有啥難的，逐個字符比較就完事了，兄弟，咱要考慮效率啊，KMP 算法相比於暴力匹配則擁有有更好的執行效率。接下來我們來學習它的實現思路。
二、KMP 字符串匹配過程推演
爲了方便大家理解，我們先通過一系列圖片，演示下 KMP 的比較過程：
假設我們有一個字符串 AD ASDFSD ASDFABBAA，我們需要校驗其是否包含 ASDFA 這個子串：
1）首先比較字符串與子串首個字符，此時是不相同的，於是子串後移一位。
2）由於 D 與 A 不同，則子串仍要後移一位。
3）就這樣不斷比較，直到出現字符串與子串首字符相同。
4）此時比較字符串與子串的下一個字符，是相等的則繼續比較。
5）直到遇到不同的字符，這時候 KMP 的優勢就會體現出來：
如果是暴力匹配，此時肯定是要將子串向後移動一位，繼續比較，但是這樣做效率真的太低了，我們通過前面幾輪的比較已經知道 ASDF 是相同的，那能否根據已知信息不再比較這些字符呢？這裏就需要引入【部分匹配表】，如下所示：
這張表是 KMP 算法的核心，關於這張表如何計算後面會講解，大家先繼續往下看。
6）此時我們知道 S 與 A 不匹配，然後前面四個字符都是匹配的，最後一個匹配字符 F 的匹配值是 0，我們通過如下公式計算子串移動位數：4 - 0 = 4。
移動位數 = 已匹配的字符數 - 對應的部分匹配值
7）移動後仍然重複前面的流程逐個字符比較，最終找到匹配的子串：
我們可以看到 KMP 可以減少比較次數從而提高計算效率，那麼這個算法最核心的【部分匹配表】是如何得到的呢？
三、部分匹配表
首先需要介紹下前綴、後綴及部分匹配值，這三個名詞的概念：
前綴：指除了最後一個字符以外，一個字符串的全部頭部組合；
後綴：指除了第一個字符以外，一個字符串的全部尾部組合
部分匹配值：就是前綴和後綴的最長的共有元素的長度。
我們以 ASDFA 爲例進行說明：
因此，我們可以明白 KMP 的實現思路就是：當一次匹配過程中在模式串 j 位置處出現字符不等時，不需要回溯主串上面的指針 i，而是利用模式串 P 在 j-1 位置的部分匹配值 k 將模式向右滑 j-k 個字符，然後繼續進行比較。
四、代碼編寫
最後我們以 Java 爲例，編寫 KMP 算法的代碼：
public class KMPDemo {
private int[] next;
private void initNext(String pattern) {
int i = 0;
int j = -1;
int len = pattern.length();
next = new int[pattern.length()];
next[0] = -1;
while(i < len - 1) {
if (j == -1 || pattern.charAt(j) == pattern.charAt(i)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
public int search(String s, String pattern) {
int i = 0;
int j = 0;
int sLen = s.length();
int pLen = pattern.length();
initNext(pattern);
while(i < sLen && j < pLen) {
if (s.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
if (next[j] == -1) {
i++;
j = 0;
} else {
j = next[j];
}
}
if (j == pLen) {
return i - j;
}
}
return -1;
}
public static void main(String[] args) {
String s = "AD ASDFSD ASDFABBAA";
String pattern = "ASDFA";
KMPDemo kmp = new KMPDemo();
System.out.println(kmp.search(s, pattern));
}本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/0bwzlzG_epm_2ouOiLOSug