题意：
给定两个字符串，你可以选择每一个字符串的非空前缀拼起来，问能拼出多少个本质不同的字符串。两个字符串长度小于等于100000。
题解：
我们考虑用所有可能的字符串减掉重复的字符串，那么显然答案就是n*m-重复个数。
那么考虑重复的时候会怎么样
如果会重复，则A+B+C=A+C+D，同时把第一个A减掉，则B+C=C+D。
这意味着什么，意味着E=F，且B=G。
观察一下E，F像什么，其实就是个kmp求出来的前缀和后缀。
这样我们对于T串每一个位置求一下最长的E，F（kmp），然后ans+=G在串S中出现的次数（二分解决），当然这里的ans是重复个数。
然后意会一下，可以知道这么做同一个东西是不会被算多次的，然后处理一下边界就行了。
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; const int INF=1313133; int n,m,nex[100002],sum[100002]; long long ans; char s[100002],t[100002]; unsigned long long has[100002],hat[100002],cf[100002]; bool pd(int x,int y,int a,int b){ if (y>n || b>m)return 0; return (has[y]-has[x-1])==(hat[b]-hat[a-1])*cf[x-a]; } int main() { scanf("%s%s",s+1,t+1);n=strlen(s+1);m=strlen(t+1); cf[0]=1; for (int i=1;i<=100000;i++)cf[i]=cf[i-1]*INF; for (int i=1;i<=n;i++)has[i]=has[i-1]+cf[i]*s[i]; for (int i=1;i<=m;i++)hat[i]=hat[i-1]+cf[i]*t[i]; for (int i=2;i<=n;i++) { int lef=0,righ=n,mid; while(lef<righ) { mid=(lef+righ+1)/2; if (pd(i,i+mid-1,1,mid))lef=mid;else righ=mid-1; } sum[lef]++; } for (int i=m;i>=1;i--)sum[i]+=sum[i+1]; nex[1]=0; for (int i=2;i<=m;i++) { int x=i-1; while(x && t[nex[x]+1]!=t[i])x=nex[x]; if (t[nex[x]+1]==t[i])nex[i]=nex[x]+1;else nex[i]=0; int a=min(nex[i],i-1); if (a)ans+=sum[i-a]; } printf("%lld ",(long long)n*m-ans); return 0; }