典型的sa题。（可能可以sam？） 两串在中间加一个奇怪字符后连起来跑sa 从大到小枚举Height，统计它的贡献。然后每次统计完并查集合并。（应该可以链表搞，，然而我wa了，，还是改成并查集）
#include <bits/stdc++.h> #define gc getchar() #define ll long long #define N 400009 using namespace std; int a[N],len1,len2,n,pos[N],isa[N],isb[N],fa[N]; char s1[N],s2[N]; ll ans; int sa[N],Rank[N],Height[N]; //sa[i]:i-th suffix's pos,Rank[i]:i-pos suffix's rank //Height[i]:sa[i]-pos suffix && sa[i-1]-pos suffix's lcp int wa[N],wb[N],wv[N],wd[N]; bool cmp(int *r,int a,int b,int l) { int x1=a+l<=n?r[a+l]:-1; int x2=b+l<=n?r[b+l]:-1; return r[a]==r[b]&&x1==x2; } bool cm(int x,int y) { return Height[x]>Height[y]; } void Get_Sa(int *r,int n,int m)//m=sigma(0~m-1) n=size of r(1-n) { int *x=wa,*y=wb; memset(wd,0,sizeof(wd)); for (int i=1;i<=n;i++) wd[x[i]=r[i]]++; for (int i=1;i<m;i++) wd[i]+=wd[i-1]; for (int i=n;i;i--) sa[wd[x[i]]--]=i; for (int j=1,p;j<=n;j<<=1,m=p) { p=0; memset(wd,0,sizeof(wd)); for (int i=n-j+1;i<=n;i++) y[++p]=i; for (int i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j; for (int i=1;i<=n;i++) wd[wv[i]=x[y[i]]]++; for (int i=1;i<m;i++) wd[i]+=wd[i-1]; for (int i=n;i;i--) sa[wd[wv[i]]--]=y[i]; swap(x,y); p=1,x[sa[1]]=0; for (int i=2;i<=n;i++) x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:(p++); if (p>=n) break; } } void Get_Height(int *r,int n) { for (int i=1;i<=n;i++) Rank[sa[i]]=i; for (int i=1,k=0;i<=n;i++) { if (k) k--; int j=sa[Rank[i]-1]; while (i+k<=n&&j+k<=n&&r[i+k]==r[j+k]) k++; Height[Rank[i]]=k; } } int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } int main() { scanf("%s",s1+1); len1=strlen(s1+1); scanf("%s",s2+1); len2=strlen(s2+1); a[0]=-1; for (int i=1;i<=len1;i++) a[++n]=s1[i]-'a'; a[++n]=26; for (int i=1;i<=len2;i++) a[++n]=s2[i]-'a'; Get_Sa(a,n,27); Get_Height(a,n); for (int i=1;i<n;i++) pos[i]=i+1; sort(pos+1,pos+n,cm); for (int i=1;i<=n;i++) { if (sa[i]<=len1) isa[i]=1; else if (sa[i]>len1+1) isb[i]=1; fa[i]=i; } for (int i=1;i<n;i++) { int l=find(pos[i]-1),r=find(pos[i]); ans+=(ll)isa[l]*isb[r]*Height[r]+(ll)isa[r]*isb[l]*Height[r]; isa[l]+=isa[r],isb[l]+=isb[r]; fa[r]=l; } printf("%lld\n",ans); return 0; }