扩展kmp

https://blog.csdn.net/dyx404514/article/details/41831947

这篇博客讲的很清楚

 求next数组:

void getnext(string s){
    int po; int len=s.length();
    nextt[0]=len; //初始化next[0]
    int pos=0;
    while(s[pos]==s[pos+1]&&pos<len-1) pos++; 
    nextt[1]=pos; //计算next[1]
    po=1; //初始化po的位置
    for(int i=2;i<len;i++){
        if(nextt[i-po]+i<po+nextt[po]) //第一种情况，可以直接得到next[i]的值
            nextt[i]=nextt[i-po];
        else{ //第二种情况，要继续匹配才能得到next[i]的值
            int j=po+nextt[po]-i;
            if(j<0) j=0;
            while(i+j<len&&s[j]==s[i+j]) j++;
            nextt[i]=j;
            po=i;
        }
        //cout<<nextt[i]<<endl;
    }
}

求extend数组

void exkmp(string a,string b){
    int len1=a.length(); int len2=b.length();
    getnext(a);
    int po; int pos=0;
    while(a[pos]==b[pos]&&pos<len1&&pos<len2) pos++;
    extend[0]=pos;
    po=0;
    for(int i=1;i<len2;i++){
        if(nextt[i-po]+i<extend[po]+po)
            extend[i]=nextt[i-po];
        else{
            int j=po+extend[po]-i;
            if(j<0) j=0;
            while(i+j<len2&&a[j]==b[i+j]&&j<len1) j++;
            extend[i]=j;
            po=i;
        }
    }
}