??什么是KMP算法?

• KMP算法是一種改進(jìn)的 字符串匹配算法，由 D.E.Knuth，J.H.Morris 和V.R.Pratt 提出的，因此人們稱它為 克努特—莫里斯—普拉特 操作（簡稱 KMP 算法）。
  • KMP 算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。
  • 具體實(shí)現(xiàn)就是通過一個 next() 數(shù)組實(shí)現(xiàn)，數(shù)組本身包含了模式串的局部匹配信息。KMP 算法的時間復(fù)雜度 $O(m+n)$。

??什么是 next() 數(shù)組 和 前綴表?

next 數(shù)組就是一個前綴表（prefix table）！

前綴表有什么作用呢

前綴表是用來回退的，它記錄了 模式串 與 主串(文本串) 不匹配的時候，模式串 應(yīng)該從哪里開始重新匹配。

我們來舉一個例子：

• 要在文本串：aabaabaafa 中查找是否出現(xiàn)過一個模式串：aabaaf。

如動畫所示：

最長公共前后綴

• 字符串的前綴是：指不包含最后一個字符的所有 以第一個字符開頭的連續(xù)子串。
• 后綴：是指不包含第一個字符的所有 以最后一個字符結(jié)尾的連續(xù)子串。

正確理解什么是前綴什么是后綴很重要!
可以理解為：最長相等前后綴

如何計算前綴表

注意字符串的前綴是指不包含最后一個字符的所有以第一個字符開頭的連續(xù)子串；后綴是指不包含第一個字符的所有以最后一個字符結(jié)尾的連續(xù)子串。

1. 長度為前1個字符的子串 a，最長相同前后綴的長度為 0 。

2. 長度為前2個字符的子串 aa ，最長相同前后綴的長度為 1 。

3. 長度為前3個字符的子串 aab，最長相同前后綴的長度為 0 。

4. 以此類推： 長度為前4個字符的子串 aaba，最長相同前后綴的長度為 1 。
5. 長度為前5個字符的子串aabaa，最長相同前后綴的長度為 2。
6. 長度為前6個字符的子串aabaaf，最長相同前后綴的長度為 0。

?? 構(gòu)造next數(shù)組

構(gòu)造 next 數(shù)組其實(shí)就是計算 模式串 s ：

• 定義兩個指針 i 和 j ，j 指向前綴末尾位置， i 指向后綴末尾位置。
• next[i] 表示 i（包括 i ）之前最長相等的前后綴長度（其實(shí)就是 j）。

next 數(shù)組就可以是前綴表，但是很多實(shí)現(xiàn)都是把 前綴表統(tǒng)一減一（右移一位，初始位置為 -1 ）之后作為 next 數(shù)組。前綴表的構(gòu)造過程，主要有如下三步：

1. 初始化:
   • j 初始化為 -1;
2. 處理前后綴不相同的情況
   • 因為 j 初始化為 -1，那么 i 就從1 開始，進(jìn)行 s[i] 與 s[j+1] 的比較;
   • 如果 s[i] 與 s[j+1] 不相同，也就是遇到 前后綴末尾不相同的情況，就要向前回退。
     • next[j] 就是記錄著 j（包括 j ）之前的子串的相同前后綴的長度;
     • 那么 s[i] 與 s[j+1] 不相同，就要找 j+1 前一個元素在 next 數(shù)組里的值（就是 next[j] ）。
3. 處理前后綴相同的情況
   • 如果 s[i] 與 s[j + 1] 相同，那么就同時向后移動 i 和 j 說明找到了相同的前后綴，同時還要將 j（前綴的長度）賦給 next[i] , 因為 next[i] 要記錄相同前后綴的長度。

構(gòu)造 next 數(shù)組的邏輯流程動畫如下：

構(gòu)造 next 數(shù)組的函數(shù)如下：（C++）

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i從1開始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后綴
            j++;
        }
        next[i] = j; // 將j（前綴的長度）賦給next[i]
    }
}

?? 使用next數(shù)組來做匹配

在文本串 s 里找是否出現(xiàn)過模式串 t。

• 定義兩個下標(biāo) j 指向模式串起始位置，i 指向文本串起始位置；
• j 初始值依然為 -1；
• 接下來就是 s[i] 與 t[j + 1] （因為 j 從 -1 開始的）進(jìn)行比較:
  • 如果 s[i] 與 t[j + 1] 不相同，j 就要從 next 數(shù)組里尋找下一個匹配的位置;
  • 如果 s[i] 與 t[j + 1] 相同，那么 i 和 j 同時向后移動。
• 如果 j 指向了模式串 t 的末尾，那么就說明模式串 t 完全匹配文本串 s 里的某個子串了。

int strStr(string haystack, string needle) {
	if (needle.size() == 0) {
	    return 0;
	}
	int next[needle.size()];
	getNext(next, needle);
	int j = -1; // // 因為next數(shù)組里記錄的起始位置為-1
	for (int i = 0; i < haystack.size(); i++) { // 注意i就從0開始
	    while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
	        j = next[j]; // j 尋找之前匹配的位置
	    }
	    if (haystack[i] == needle[j + 1]) { // 匹配，j和i同時向后移動
	        j++; // i的增加在for循環(huán)里
	    }
	    if (j == (needle.size() - 1) ) { // 文本串s里出現(xiàn)了模式串t
	        return (i - needle.size() + 1);
	    }
	}
	return -1;
}

匹配過程如下：

時間復(fù)雜度: $O(n+m)$。
空間復(fù)雜度: $O(m)$, 只需要保存字符串 needle 的前綴表。

放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁 / CSDN—力扣專欄，每日更新！

注：僅供學(xué)習(xí)參考，如有不足，歡迎指正！文章來源地址http://www.zghlxwxcb.cn/news/detail-471808.html

到了這里，關(guān)于一文搞懂KMP算法?。。〉奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！