扩展KMP的next数组求的是子字符串的每一个位置！！和KMP算法的next数组有所区别

即子字符串的每一个位置和子字符串的第一个位置的最长前缀

代码：

void getnext(char s[],int len)
{
    int i=0,j,pos;
    next[0] = len;
    while(s[i] == s[i+1] && i+1 < len)
        i++;
    next[1] = i;
    pos = 1;
    for(i=2;i<len;i++){
        if(next[i-pos]+i < next[pos]+pos)
            next[i] = next[i-pos];
        else{
            j=next[pos]+pos-i;
            if(j<0)j=0;
            while(i+j < len && s[j] == s[j+i])
                j++;
            next[i]=j;
            pos = i;
        }
    }
}
//1231231234
//10 0 0 6 0 0 3 0 0 0

扩展KMP实现，其实相当于写了俩遍的getnext

#include <bits/stdc++.h>
using namespace std;
const int maxx = 10010;
int next[maxx],ans[maxx];
void getnext(char s[],int len)
{
    int i=0,j,pos=1;
    next[0] = len;
    while(s[i] == s[i+1] && i+1 < len)
        i++;
    next[1] = i;
    for(i=2;i<len;i++){
        if(next[i-pos]+i < next[pos]+pos)
            next[i] = next[i-pos];
        else{
            j=next[pos]+pos-i;
            if(j<0)j=0;
            while(i+j < len && s[j] == s[j+i])
                j++;
            next[i]=j;
            pos = i;
        }
    }
}

void exkmp(char s1[],int l1,char s2[],int l2)
{
    int i=0,j,pos=0;
    getnext(s2,l2);
    while(s1[i] == s2[i] && i<l2 && i<l1)
        i++;
    ans[0] = i;
    for(i=1;i<l1;i++){
        if(next[i-pos]+i < ans[pos] + pos)
            ans[i] = next[i-pos];
        else{
            j=ans[pos]+pos-i;
            if(j<0)j=0;
            while(i+j<l1&&j<l2&&s1[j+i]==s2[j])
                j++;
            ans[i]=j;
            pos=i;
        }
    }
}
char s1[maxx],s2[maxx];
int main(){
    scanf("%s",s1);
    scanf("%s",s2);
    int l1 = strlen(s1),l2 = strlen(s2);
    exkmp(s1,l1,s2,l2);
    for(int i=0;i<l1;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}