题目：
每个后缀结尾处 ct[ ] = 1 ，按拓扑序 dp 一下就能求出 right 集合的大小。自动机上每个点的贡献就是 ( l [cr]-l [fa] ) * ct[0][cr] * ct[1][cr] ， ct[0] 和 ct[1] 表示在两个字符串里分别的出现次数。
#include#include #include #define ll long longusing namespace std;const int N=2e5+5,M=8e5+5,K=30;int tot=1,go[M][K],fa[M],l[M],ct[2][M],ans[M];char s[2][N]; int q[M],tx[N],vis[M];int cz(int p,int w){ int q=go[p][w],nq=++tot;l[nq]=l[p]+1; fa[nq]=fa[q];fa[q]=nq; memcpy(go[nq],go[q],sizeof go[q]); for(;p&&go[p][w]==q;p=fa[p])go[p][w]=nq; return nq;}int ins(int p,int w){ if(go[p][w]) { int q=go[p][w]; if(l[q]==l[p]+1)return q; return cz(p,w); } int np=++tot;l[np]=l[p]+1; for(;p&&!go[p][w];p=fa[p])go[p][w]=np; if(!p)fa[np]=1; else { int q=go[p][w]; if(l[q]==l[p]+1)fa[np]=q; else fa[np]=cz(p,w); } return np;}void Rsort(int n){ for(int i=1;i<=tot;i++)tx[l[i]]++; for(int i=1;i<=n;i++)tx[i]+=tx[i-1]; for(int i=1;i<=tot;i++)q[tx[l[i]]--]=i;}int main(){ scanf("%s",s[0]);scanf("%s",s[1]); int n[2];n[0]=strlen(s[0]);n[1]=strlen(s[1]); for(int t=0;t<=1;t++) for(int pr=1,i=0;i