扩展kmp是用来解决字符串b与字符串a的各个后缀的最长公共前缀的问题。
题目参考：
洛谷P5410
算法思路：
设\(nxt[i]\)为b以第i个字符为头的后缀，\(nxtb[i]\)为a以第i个字符为头的后缀。
当我们已知\(a[l\dots r]=b[1\dots r-l+1](a[l\dots r]表示字符串a从l到r区间的字符串)\)，且\(i\le r\)，\(nxtb[i]=\min(nxt[i-l+1],r-i+1)\)，求\(nxt[i]\)的方法相同，然后while向后找就可以了。
证明：
\(a[l\dots r]=b[1\dots r-l+1]\)所以当\(i\le r\)时\(a[i\dots r]=b[i-l+1\dots r-l+1]\)
\(nxtb[i]=\min(nxt[i-l+1],r-i+1)\)
复杂度：
\(nxt[i-l+1]<r-i+1\)时，不会用到while更新。
\(nxt[i-l+1]\ge r-i+1\)时，r只会增加且最多增加n次。
注意：
循环从i=2开始，\(nxt[1]\)、\(nxtb[1]\)需要特殊计算。
代码：
#include<iostream>
#include<cstring>
using namespace std;
char a[20000010],b[20000010];
int nxt[20000010],nxtb[20000010];
long long ans=0;
int n,m;
int main(){
scanf("%s",a+1);
n=strlen(a+1);
scanf("%s",b+1);
m=strlen(b+1);
int l=0,r=0;
for(int i=2;i<=m;i++){
if(r>=i){
nxt[i]=min(nxt[i-l+1],r-i+1);
}
while(i+nxt[i]<=m&&b[i+nxt[i]]==b[nxt[i]+1]){
nxt[i]++;
}
if(r<=i+nxt[i]-1){
r=i+nxt[i]-1;
l=i;
}
ans=ans^(1ll*i*(nxt[i]+1));
}
nxt[1]=m;
ans=ans^(1ll*(nxt[1]+1));
cout<<ans<<endl;
l=0,r=0;
ans=0;
while(1+nxtb[1]<=n&&nxtb[1]+1<=m&&a[1+nxtb[1]]==b[nxtb[1]+1]){
nxtb[1]++;
}
ans=1ll*(nxtb[1]+1);
for(int i=2;i<=n;i++){
if(r>=i){
nxtb[i]=min(nxt[i-l+1],r-i+1);
}
while(i+nxtb[i]<=n&&nxtb[i]+1<=m&&a[i+nxtb[i]]==b[nxtb[i]+1]){
nxtb[i]++;
}
if(r<=i+nxtb[i]-1){
r=i+nxtb[i]-1;
l=i;
}
ans=ans^(1ll*i*(nxtb[i]+1));
}
cout<<ans;
return 0;
}