【XSY3458】原样输出（SAM）

考虑判断一个串是否能成为输出，贪心的方法肯定是优先在第一个串的 SAM 上匹配至匹配不了，再在第二个串的 SAM 上匹配至匹配不了，……

于是可以考虑通过如下方式把 \(n\) 个串的 SAM 拼起来：

如果一个点没有 \(C\) 的转移边，那么就要向之后第一个包含字符 \(C\) 的字符串的后缀自动机接受字符串 \(C\) 的节点连一条 \(C\) 的转移边。

然后询问就是拓扑排序 DP（type=0）和暴力 dfs（type=1）。

#include<bits/stdc++.h>

#define N 3000010
#define NN 6000010
#define re register

using namespace std;

int n;
int cid[26];
int nrt,lst,node,ch[NN][4],len[NN],fa[NN];
bool root[NN];
char str[N];
char idc[4];

void insert(int c)
{
	int p=lst,now=lst=++node;
	len[now]=len[p]+1;
	for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=now;
	if(!p) fa[now]=nrt;
	else
	{
		int q=ch[p][c];
		if(len[q]==len[p]+1) fa[now]=q;
		else
		{
			int nq=++node;
			memcpy(ch[nq],ch[q],sizeof(ch[nq]));
			len[nq]=len[p]+1;
			fa[nq]=fa[q],fa[q]=nq;
			fa[now]=nq;
			for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
		}
	}
}

void build()
{
	nrt=lst=++node;
	root[nrt]=1;
	for(int i=1,len=strlen(str+1);i<=len;i++)
		insert(cid[str[i]-'A']);
}

void work()
{
	int nxtrt=-1;
	for(int i=node;i>=1;i--)
	{
		if(nxtrt!=-1)
		{
			for(int c=0;c<4;c++)
				if(!ch[i][c]) ch[i][c]=ch[nxtrt][c];
		}
		if(root[i]) nxtrt=i;
	}
}

namespace sub0
{
	namespace modular
	{
		const int mod=1000000007;
		inline void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
	}using namespace modular;
	bool vis[NN];
	int d[NN],f[NN];
	queue<int>q;
	void dfs(int u)
	{
		vis[u]=1;
		for(int c=0;c<4;c++)
		{
			if(ch[u][c])
			{
				d[ch[u][c]]++;
				if(!vis[ch[u][c]]) dfs(ch[u][c]);
			}
		}
	}
	void main()
	{
		dfs(1);
		q.push(1);
		f[1]=1;
		int ans=0;
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			Add(ans,f[u]);
			for(int c=0;c<4;c++)
			{
				if(ch[u][c])
				{
					d[ch[u][c]]--;
					Add(f[ch[u][c]],f[u]);
					if(!d[ch[u][c]]) q.push(ch[u][c]);
				}
			}
		}
		printf("%d\n",ans);
	}
}

namespace sub1
{
	int ans;
	int len;
	int top;
	char now[N],out[10000000];
	void dfs(int u)
	{
		ans++;
		now[len+1]='\n';
		for(int i=1;i<=len+1;i++) out[++top]=now[i];
		if(top>=5000000)
		{
			fwrite(out+1,top,sizeof(char),stdout);
			top=0;
		}
		len++;
		for(int c=0;c<4;c++)
		{
			if(ch[u][c])
			{
				now[len]=idc[c];
				dfs(ch[u][c]);
			}
		}
		len--;
	}
	void main()
	{
		dfs(1);
		if(top) fwrite(out+1,top,sizeof(char),stdout);
		printf("%d\n",ans);
	}
}

int main()
{
	cid['A'-'A']=0,cid['C'-'A']=1,cid['G'-'A']=2,cid['T'-'A']=3;
	idc[0]='A',idc[1]='C',idc[2]='G',idc[3]='T';
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		build();
	}
	work();
	int k;
	scanf("%d",&k);
	if(k) sub1::main();
	else sub0::main();
	return 0;
}