//next[i]： T[i]…T[m - 1]与T的最长相同前缀长度；
//extend[i]： S[i]…S[n - 1]与T的最长相同前缀长度。
char p[10005],s[1000005];
int nexts[100005],extend[1000005];
void getNEXT(char*p,int &plen,int *nexts){
int a=0,k=0;
nexts[0]=plen;
for(int i=1;i<plen;i++){
if(i>=k||i+nexts[i-a]>=k){
if(i>=k) k=i;
while(k<plen&&p[k]==p[k-i])
k++;
nexts[i]=k-i;
a=i;
}
else
nexts[i]=nexts[i-a];
}
}
void extendkmp(char*s,int&slen,char*p,int &plen,int *extend, int *next){
int a=0,k=0;
getNEXT(p,plen,next);
for(int i=0;i<slen;i++){
if(i>=k||i+nexts[i-a]>=k){
if(i>=k) k=i;
while(k<slen&&k-i<plen&&s[k]==p[k-i])
k++;
extend[i]=k-i;
a=i;
}
else
extend[i]=nexts[i-a];
}
}
