KMP简洁模板

代码

int strStr(string haystack, string needle) {
    if(needle.size()==0) return 0;
    int* nxt = new int[needle.length()];
    getNext(needle,nxt);
    for(int i=0,j=0;i<haystack.size();i++){
        while(j>0&&haystack[i]!=needle[j]) j = nxt[j-1];
        if(haystack[i]==needle[j]) j++;
        if(j==needle.size()) return i-j+1;
    }
    return -1;
}
void getNext(string pat,int* nxt){
    int pLen = pat.length();
    nxt[0] = 0;
    for(int i = 1,j = 0;i<pLen;i++){
        while(j>0&&pat[i]!=pat[j]) j=nxt[j-1];
        if(pat[i]==pat[j]) j++;
        nxt[i] = j;
    }
}