1.什么是KMP

是由這三位學者發明的：Knuth，Morris和Pratt，所以取了三位學者名字的首字母，所以叫做KMP

2.KMP的用處

KMP主要用于字串匹配，KMP的主要思想是當出現字串不匹配時，可以知道一部分之前已經匹配的文本內容，可以利用這些資訊避免從頭再去做匹配了，

3.最長公共前后綴

字串的前綴是指不包含最后一個字符的所有以第一個字符開頭的連續子串，后綴是指不包含第一個字符的所有以最后一個字符結尾的連續子串，正確理解什么是前綴什么是后綴很重要! 前綴表要求的就是相同前后綴的長度，

字串a的最長相等前后綴為0，字串aa的最長相等前后綴為1，字串aaa的最長相等前后綴為2，

4.前綴表

如果接觸過KMP的同學，一定都寫過next陣列，next陣列就是一個前綴表，前綴表是用來回退的，它記錄了模式串與主串(文本串)不匹配的時候，模式串應該從哪里開始重新匹配，

要在文本串：aabaabaafa 中查找是否出現過一個模式串：aabaaf，如下所示（來自代碼隨想錄）：

為啥我們一定需要前綴表嘞？

剛剛匹配的程序在下標5的地方遇到不匹配，模式串是指向f，如圖：

然后就找到了下標2，指向b，繼續匹配：如圖：

下標5之前這部分的字串（也就是字串aabaa）的最長相等的前綴和后綴字串是子字串aa ，因為找到了最長相等的前綴和后綴，匹配失敗的位置是后綴子串的后面，那么我們找到與其相同的前綴的后面重新匹配就可以了，

所以前綴表具有告訴我們當前位置匹配失敗，跳到之前已經匹配過的地方的能力，

5.計算前綴表

如圖：

KMP精講5 KMP精講6

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

KMP精講7 KMP精講8

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

把求得的最長相同前后綴的長度就是對應前綴表的元素，如上圖：

可以看出模式串與前綴表對應位置的數字表示的就是：下標i之前（包括i）的字串中，有多大長度的相同前綴后綴，

如何利用前綴表找到當字符不匹配的時候應該指標應該移動的位置？如影片所示：

KMP精講2

找到的不匹配的位置，那么此時我們要看它的前一個字符的前綴表的數值是多少，前一個字符的前綴表的數值是2，所以把下標移動到下標2的位置繼續比配，可以再反復看一下上面的影片，最后就在文本串中找到了和模式串匹配的子串了

最后我們就可以來利用該陣列進行匹配了

6.kmp演算法代碼實作

構造next陣列其實就是計算模式串s，前綴表的程序，主要有如下三步：

初始化
處理前后綴不相同的情況
處理前后綴相同的情況

定義兩個指標i和j，j指向前綴末尾位置，i指向后綴末尾位置，然后還要對next陣列進行初始化賦值，如下：

int j = -1;
next[0] = j;

初始化為-1，是對next陣列-1的一種操作，前綴表會涉及一種+1 -1操作

當前后綴不相同的時，j初始化為-1，那么i就從1開始，進行s[i] 與 s[j+1]的比較，

所以遍歷模式串s的回圈下標i 要從 1開始，代碼如下：

for (int i = 1; i < s.size(); i++) {

如果 s[i] 與 s[j+1]不相同，也就是遇到前后綴末尾不相同的情況，就要向前回退，就要找 j+1前一個元素在next陣列里的值（就是next[j]），

　　所以，處理前后綴不相同的情況，代碼如下：

while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了
    j = next[j]; // 向前回退
}

當前后綴相同的時，s[i] 與 s[j + 1] 相同，那么就同時向后移動i 和j 說明找到了相同的前后綴，同時還要將j（前綴的長度）賦給next[i], 因為next[i]要記錄相同前后綴的長度，

if (s[i] == s[j + 1]) { // 找到相同的前后綴
    j++;
}
next[i] = j;

怎么樣，一頓操作下來是不是感覺簡單很多了，要理解kmp演算法的思路！！！

完整代碼如下：

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        int[] next=new int[needle.length()];
        int j=-1;
        getNext(next, needle);
        for(int i=0; i<haystack.length(); i++){
            while(j>=0 && haystack.charAt(i)!=needle.charAt(j+1)){
                j=next[j];
            }
            if(haystack.charAt(i)==needle.charAt(j+1)){
                j++;
            }
            if(j==needle.length()-1){
                return (i-needle.length()+1);
            }
        }
        return -1;
    }

    public void getNext(int[] next,String s){
        int j=-1;
        next[0]=j;
        for(int i=1; i<s.length(); i++){
            while(j>=0 && s.charAt(i)!=s.charAt(j+1)){
                j=next[j];
            }
            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i]=j;
        }
    }

}

時間復雜度分析：

其中n為文本串長度，m為模式串長度，因為在匹配的程序中，根據前綴表不斷調整匹配的位置，可以看出匹配的程序是O(n)，之前還要單獨生成next陣列，時間復雜度是O(m)，所以整個KMP演算法的時間復雜度是O(n+m)的，

暴力的解法顯而易見是O(n × m)，所以KMP在字串匹配中極大地提高了搜索的效率，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539459.html

標籤：其他

上一篇：Chatgpt注冊全流程教程