原文链接https://www.cnblogs.com/zhouzhendong/p/CF542E.html

题意

　　给定三个字符串 $s1,s2,s3$ ，对于所有 $L\in{1,2,\cdots,min(|s1|,|s2|,|s3|)}$ ，输出 $f(L)$ 。

　　其中 $f(L)$ 表示满足 $s_k[i_k,\cdots,i_k+L-1]$ 全部相同的 $i_1,i_2,i_3$ 的个数。

　　答案对 $10^9+7$ 取模。

　　$|s1|+|s2|+|s3|\leq 3\times 10^5$

题解

　　第二次写广义后缀自动机，居然又只写了 20 分钟？？然而没有看到取模，以及一个取模上面的傻逼错误续了我 15 分钟。

　　把三个串全部扔进广义后缀自动机里面。

　　对于每一个状态，分别算出属于这三个串的 right 集合大小。

　　然后对于每一个节点，方案总数就是 $\prod_{k=0}^{2}right_{i,k}$ ，影响的长度范围是 $(\rm{Max(father),Max(i)}]$ ，相当于区间加，直接差分一下就可以了。

　　最后回答的时候前缀和一下就好了。注意取模。

代码

#include 
     
      #define right __fjw82using namespace std;const int N=300005,S=N*2,mod=1e9+7;char s[N];int n=1e9,in[S],q[S],ans[N],right[S][3],head,tail;int root,size;struct SAM{	int Next[26],fa,Max;}t[N<<1];void init(){	memset(t,0,sizeof t);	root=size=1;	t[0].Max=-1;	for (int i=0;i<26;i++)		t[0].Next[i]=1;}int extend(int p,int c){	if (t[p].Next[c]&&t[p].Max+1==t[t[p].Next[c]].Max)		return t[p].Next[c];	int np=++size,q,nq;	t[np].Max=t[p].Max+1;	for (;!t[p].Next[c];p=t[p].fa)		t[p].Next[c]=np;	q=t[p].Next[c];	if (t[p].Max+1==t[q].Max)		t[np].fa=q;	else {		nq=++size;		t[nq]=t[q],t[nq].Max=t[p].Max+1;		t[q].fa=t[np].fa=nq;		for (;t[p].Next[c]==q;p=t[p].fa)			t[p].Next[c]=nq;	}	return np;}int main(){	init();	for (int i=0,now;i<3;i++){		scanf("%s",s+1);		n=min(n,now=strlen(s+1));		for (int j=1,p=root;j<=now;j++)			right[p=extend(p,s[j]-'a')][i]++;	}	for (int i=2;i<=size;i++)		in[t[i].fa]++;	head=tail=0;	for (int i=2;i<=size;i++)		if (in[i]==0)			q[++tail]=i;	while (head
      
       1&&!in[t[x].fa])			q[++tail]=t[x].fa;	}	memset(ans,0,sizeof ans);	for (int i=2;i<=size;i++){		int add=1LL*right[i][0]*right[i][1]*right[i][2]%mod;		(ans[t[t[i].fa].Max+1]+=add)%=mod;		(ans[t[i].Max+1]+=mod-add)%=mod;	}	for (int i=1;i<=n;i++){		ans[i]=(ans[i]+ans[i-1])%mod;		printf("%d ",ans[i]);	}	return 0;}