c++KMP字符串匹配算法

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;
    }
};

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]){//前后缀相同，前缀指针前进一位
                prefix++; 
            }
            next[suffix]=prefix;//更新next数组，prefix走到哪说明就有多少的相同的前后缀
        }
    }

int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;
        int next[needle.size()];
        get_next(next,needle);
        int j=0;
        //定义两个下标j指向模版串起始位置，i指向文本串起始位置
        for(int i=0;i<haystack.size();i++){
            while(j>0 && haystack[i]!=needle[j]){ //模版串j位置和文本串i位置不相同，j利用next数组回退到上一个相同的位置继续匹配
                j=next[j-1];
            }
            if(haystack[i]==needle[j]){  //模版串j位置和文本串i位置相同
                j++;
            }
            if(j==needle.size()){  //找到匹配的字符串
                return (i-needle.size()+1); //返回匹配的字符串起始位置
            }
        }
        return -1;
    }