题目描述：
nealchen 是一只 copycat。 它会把输入按行读入，原封不动地复制到输出中去。 但是在一次更新以后，它的程序出了一些问题。 它没法输出换行符了。 并且，读入的时候，总会莫名其妙地随机漏掉开头和结尾的若干个字符，甚至整行 都会漏掉。 比如 orznight 可能会变成 rzni ，orz，h 或者空串。 现在你找到一份输入文件丢给 nealchen，你想知道它的输出可能有多少种情况，以 及每种情况分别是什么。 由于你找到的输入文件全部来自之前的福建省选，所以所有的输入文件每行只可 能包含 $A,C,G,T$ 四种字符。
输入：
第一行一个正整数 $n$ ，表示（题面中）输入文件的行数。 接下来 $n$ 行，表示输入文件的内容。保证这 $n$ 行中每行的每个字符是 $A.C,G,T$ 四种字符中的一种。 接下来一个整数 $k(0≤k≤1)$ ，具体含义详见输出格式。
输出：
若 $k=0$ ，你需要输出一行，表示输出的可能情况个数模 $10^{9}+7$ 的结果。 若 $k=1$ ，你需要按照字典序从小到大输出所有可能的输出情况，一行一个字符 串，最后一行输出输出的可能情况个数模 $10^{9}+7$ 的结果。
算法标签：后缀自动机
思路：
考虑对于一个字符串，你要去判断他是否能由给的字符串生成，此时我们会去贪心的匹配。
所以考虑反着想，我们建出对于每个串分别建后缀自动机，考虑对于一个节点如果存在关于 $a$ 的边，那我们会贪心的匹配继续往下走，否则我们会在之后的第一个出现a的地方继续匹配。于是我们联通一条当前点连向之后第一个有 $a$ 的串的点，也就是某一个串的根节点的儿子上。
之后相当于一个有向图，可以dfs统计答案或者拓扑统计答案。
以下代码：
#include#define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=2e6+5,p=1e9+7;char res[N],s[N];int n,rt[N],ch[N][4],fa[N],last,cur=1,d[N],cnt=1;int nxt[N][4],f[N],ans,lst[4];il int read(){ int x,f=1;char ch; _(!)ch=='-'?f=-1:f;x=ch^48; _()x=(x<<1)+(x<<3)+(ch^48); return f*x;}il int Ci(char cc){ if(cc=='A')return 0; if(cc=='C')return 1; if(cc=='G')return 2; if(cc=='T')return 3;}il char Co(int x){ if(x==0)return 'A'; if(x==1)return 'C'; if(x==2)return 'G'; if(x==3)return 'T';}il int mu(int x,int y){ if(x+y>=p)return x+y-p; return x+y;}il void build(int c,int id,int rot){ last=cur;cur=++cnt;d[cur]=id; int p=last; for(;p&&!ch[p][c];p=fa[p])ch[p][c]=cur; if(!p)fa[cur]=rot; else{ int q=ch[p][c]; if(d[q]==d[p]+1)fa[cur]=q; else{ int nt=++cnt;d[nt]=d[p]+1; memcpy(ch[nt],ch[q],sizeof(ch[q])); fa[nt]=fa[q];fa[q]=fa[cur]=nt; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt; } }}il int dp1(int rot,int x){ if(f[x])return f[x]; f[x]=1; for(int i=0;i<4;i++){ if(ch[x][i])f[x]=mu(f[x],dp1(rot,ch[x][i])); else if(nxt[rot][i]) f[x]=mu(f[x],dp1(nxt[rot][i],ch[rt[nxt[rot][i]]][i])); } return f[x];}il void prin(int l){ for(int i=1;i<=l;i++)putchar(res[i]); putchar('\n'); ans++;}il void dp2(int rot,int x,int tot){ prin(tot); for(int i=0;i<4;i++){ res[tot+1]=Co(i); if(ch[x][i])dp2(rot,ch[x][i],tot+1); else if(nxt[rot][i]) dp2(nxt[rot][i],ch[rt[nxt[rot][i]]][i],tot+1); }}int main(){ freopen("copy.in","r",stdin); freopen("copy.out","w",stdout); n=read(); for(int i=1;i<=n;i++){ scanf(" %s",s+1); cur=rt[i]=++cnt; int l=strlen(s+1); for(int j=1;j<=l;j++)build(Ci(s[j]),j,rt[i]); } for(int i=0;i<4;i++) if(ch[rt[n]][i])lst[i]=ch[rt[n]][i]; for(int i=n-1;i;i--){ for(int j=0;j<4;j++){ if(ch[rt[i+1]][j])nxt[i][j]=i+1; else nxt[i][j]=nxt[i+1][j]; } } int op=read(); if(!op){ printf("%d\n",dp1(1,rt[1])); } else{ dp2(1,rt[1],0); printf("%d\n",ans); } return 0;}