kmp没写过，扩展kmp没学过可还行。
两个愿望，一次满足
（该博客仅用于防止自己忘记，不保证初学者能看懂我在瞎bb什么qwq）
用途
对于串\(s1,s2\)，可以求出\(s2\)与\(s1\)的每个后缀的最长公共前缀。
（其实SA也可以干这事，只不过复杂度多个\(\log\)可能会被卡）
思想
与kmp一样，主要是充分利用已经得到的信息来往下推，以降低复杂度。
暴力
\(O(n^2)\)暴力扫，相信大家都会？
优化
记\(s[l,r]\)表示\(s\)在\([l,r]\)的子串。
考虑这样一件事：假如\(s2[1,k]=s1[1,k]\)，那么就可以知道\(s2[2,k]=s1[2,k]\)。
假如再知道\(s2[2,p]=s2[1,p-1]\)，那么就可以推出\(s2[1,\min(p,k)-1]=s1[2,k]\)了。
\(s2[2,p]=s2[1,p-1]\)正是kmp中\(s2\)的\(nxt\)数组，于是这样就可以完成一次转移。
然而这样转移并不是很优：当\(p<k\)时显然不能再往后推，但\(p>k\)时往后推还需要\(O(n)\)的时间，总复杂度仍然是\(O(n^2)\)的。
但我们可以记录之前最大的\(k\)在哪里，于是\(k_{max}\)单调递增，复杂度就有保证了。
代码
由于求nxt和求ex代码非常像，于是缩到了一起。
int n,m;
char s1[sz],s2[sz];
int nxt[sz],ex[sz];
void ExKmp(char *s1,char *s2,int *nxt,int *ex)
{
int len1=strlen(s1+1),len2=strlen(s2+1);
if (s1!=s2) for (ex[1]=0;s1[ex[1]+1]==s2[ex[1]+1]&&ex[1]<min(len1,len2);ex[1]++);
else {nxt[1]=len1;while (s1[nxt[2]+1]==s1[nxt[2]+2]&&nxt[2]+2<=len1) ++nxt[2];}
int p=1+(s1==s2);
rep(i,2+(s1==s2),len1)
{
if (i+nxt[i-p+1]<p+ex[p]) ex[i]=nxt[i-p+1];
else
{
int k=max(p+ex[p]-i,0);
while (s1[i+k]==s2[k+1]) ++k;
ex[i]=k;p=i;
}
}
}
int main()
{
file();
cin>>(s1+1)>>(s2+1);
n=strlen(s1+1),m=strlen(s2+1);
ExKmp(s2,s2,nxt,nxt);ExKmp(s1,s2,nxt,ex);
rep(i,1,m) printf("%d ",nxt[i]);
puts("");
rep(i,1,n) printf("%d ",ex[i]);
return 0;
}