class Solution {
public:
    int strStr(string haystack, string needle) {
        int n=haystack.size(),m=needle.size();
        if(m==0) return 0;
        for(int i=0;i<n;i++){
            if(haystack[i]==needle[0]){
                for(int j=0;j<m;j++){
                    if(haystack[i+j]!=needle[j])
                        break;
                    if(j==m-1) return i;
                }
            }
        }
        return -1;
    }
};

可見暴力匹配過程中實現(xiàn)的是一個雙層循環(huán)，那么算法的時間復(fù)雜度較高，為О(n*m)，然而KMP的算法時間復(fù)雜度僅為О(n+m)，其算法性能明顯提高，具體時間復(fù)雜度計算方法后面介紹。

前綴表

KMP算法中一個重要的概念就是前綴表（prefix table），并用一維數(shù)組 next 記錄前綴信息實際上next數(shù)組就是一個前綴表。

了解前綴表我們首先需要了解前綴和后綴的區(qū)別，此處的前綴是指不包含最后一個字符的所有以第一個字符開頭的連續(xù)子串，后綴是指不包含第一個字符的所有以最后一個字符結(jié)尾的連續(xù)子串。比如字符串“abac”的前綴有“a”, "ab”, "aba”，字符串“abac”的后綴有“c”,"ac”，"bac”。

前綴表第 i 個位置存的值 next[i] 代表[0,i]這個字符串最長的相同前后綴的長度，比如字符串“abbc”的 next[3]為 0 ,next[2]為 1 ("aba”的前綴有“a”, "ab”，后綴有“a”,"ba”)。

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

KMP算法的核心思想就是先求出匹配模板的next數(shù)組，再運(yùn)用next數(shù)組進(jìn)行字符串匹配。

如何構(gòu)造前綴表next數(shù)組

void get_next(int *next,string t){ //t為模板字符串
        //定義兩個指針prefix和suffix，prefix指向前綴起始位置，suffix指向后綴起始位置
        int prefix=0;
        next[prefix]=0;
        for(int suffix=1;suffix<t.size();suffix++){
            while(prefix>0 && t[suffix]!=t[prefix]){//前后綴不相同，前綴指針向前回退
                prefix=next[prefix-1];
            }
            if(t[suffix]==t[prefix]){//前后綴相同，前綴指針前進(jìn)一位
                prefix++; 
            }
            next[suffix]=prefix;//更新next數(shù)組，prefix走到哪說明就有多少的相同的前后綴
        }
    }

如何用next數(shù)組進(jìn)行模板匹配

int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;
        int next[needle.size()];
        get_next(next,needle);
        int j=0;
        //定義兩個下標(biāo)j指向模版串起始位置，i指向文本串起始位置
        for(int i=0;i<haystack.size();i++){
            while(j>0 && haystack[i]!=needle[j]){ //模版串j位置和文本串i位置不相同，j利用next數(shù)組回退到上一個相同的位置繼續(xù)匹配
                j=next[j-1];
            }
            if(haystack[i]==needle[j]){  //模版串j位置和文本串i位置相同
                j++;
            }
            if(j==needle.size()){  //找到匹配的字符串
                return (i-needle.size()+1); //返回匹配的字符串起始位置
            }
        }
        return -1;
    }

由此可見構(gòu)造next數(shù)組的時間復(fù)雜度是О(m)，利用next數(shù)組進(jìn)行匹配的時間復(fù)雜度是О(n)，總的時間復(fù)雜度是О(n+m)