KMP&EXKMP

void getnx(char *str){
    //nx[i] 是str[1..x]与str[y..i]的最大公共前缀长度 x<i,y>1
    int len=strlen(str);int i=0,k=-1;nx[0]=-1;
    while(i<len)if(k==-1||str[i]==str[k])nx[++i]=++k;else k=nx[k];
}
int index(char *str,char *p){
    int i=0,j=0;int len1=strlen(str),len2=strlen(p);
    if(len1==1&&len2==1)if(str[0]==p[0])return 0;else return -1;
    int nx[N];getnx(p,nx);
    while(i<len1&&j<len2)
    if(j==-1||str[i]==p[j])i++,j++;else j=nx[j];
    if(j==len2)return i-len2;else return -1;
}
int Count(char *str,char *p){
    int ans=0,i=0,j=0;int nx[N];
    int len1=strlen(str),len2=strlen(p);
    if(len1==1&&len2==1)if(str[0]==p[0])return 1;else return 0;
    getnx(p,nx);
    for(i=0;i<len1;i++){
        while(j>0&&str[i]!=p[j])j=nx[j];
        if(str[i]==p[j])j++;
        if(j==len2)ans++,j=nx[len2];
    }
    return ans;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char s1[N],s2[N];
int z[N],mix=0,L=0;
int main(){
    scanf("%s%s",&s2,&s1);
    int n=strlen(s1);
    strcat(s1,"#");strcat(s1,s2);
    for(int i=1;s1[i];i++){
        if(i>=mix)z[i]=0;
        else z[i]=min(mix-i,z[i-L]);
        while(s1[z[i]]==s1[z[i]+i])z[i]++;
        if(i+z[i]>mix)mix=i+z[i],L=i;
    }
    for(int i=0;i<n;i++)printf("%d%c",z[i]," \n"[i==n-1]);//s1的每一个后缀与s1[1..n]最大公共前缀长度
    for(int i=n+1;s1[i];i++)cout<<z[i]<<' ';//s2的每一个后缀与s1[1..n]最大公共前缀长度
}