YZOJ P4258 [FJWC2019]原样输出
时间限制：4000MS 内存限制：262144KB
出题人：E.Space 难度：\(7.0\)
-
题目描述
它会把输入按行读入，原封不动地复制到输出中去。
但是在一次更新以后，它的程序出了一些问题。
它没法输出换行符了。
并且，读入的时候，总会莫名其妙地随机漏掉开头和结尾的若干个字符，甚至整行都会漏掉。
比如 orzxxxxx 可能会变成 rzxx、orz、x 或者空串。
现在你找到一份输入文件丢给它，你想知道它的输出可能有多少种情况，以及每种情况分别是什么。
由于你找到的输入文件全部来自之前的福建省选，所以所有的输入文件每行只可能包含 A、C、G、T 四种字符。
-
输入格式
第一行一个正整数 \(n\)，表示（题面中）输入文件的行数。
接下来 \(n\) 行，表示输入文件的内容。保证这 \(n\) 行中每行的每个字符是 A、C、G、T 四种字符中的一种。
接下来一个整数 \(k, (0 \leq k \leq 1)\)，具体含义详见输出格式。
-
输出格式
若 \(k=0\)，你需要输出一行，表示输出的可能情况个数模 \(10^9+7\) 的结果。
若 \(k=1\)，你需要按照字典序从小到大输出所有可能的输出情况，一行一个字符串，最后一行输出输出的可能情况个数模 \(10^9+7\) 的结果。
-
样例输入
|
1 2 3 4 5 |
3 AC CC AA 1 |
-
样例输出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
A AA AAA AC ACA ACAA ACC ACCA ACCAA ACCC ACCCA ACCCAA C CA CAA CC CCA CCAA CCC CCCA CCCAA 22 |
-
数据规模与约定
对于 \(100\%\) 的数据，保证输入文件大小不超过 \(1MB\) ，保证输出文件大小不超过 \(200MB\) 。
考虑后缀自动机，\(k=0\) 统计本质串的数量即可，\(k=1\) 时直接按照字典序爆搜。
关键是SAM怎么建。
要建立一个恰好能识别题目所有串的自动机，那么就是在每一个后缀自动机上没有某一字符出边的节点上，把该字符对应的出边连到最近的一个后缀自动机上。
这样贪心的匹配，自动机恰好能识别所有串。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define MOD 1000000007 inline void getstr(char s[],int&ls) { register char c=0; while(!(c>='A' && c<='Z')) c=getchar(); ls=0; while(c>='A' && c<='Z') s[++ls]=c,c=getchar(); s[ls+1]=0; return; } #define MapChar(_x) ((_x)=='A'?0:((_x)=='C'?1:((_x)=='G'?2:3))) #define GetChar(_x) ((_x)==0?'A':((_x)==1?'C':((_x)==2?'G':'T'))) struct SAM { int root,last; }sam[2550505]; int cnt,parent[2550505],mxval[2550505],ch[2550505][4]; inline int CreateNode(register int val=0) { cnt++,parent[cnt]=0,mxval[cnt]=val; for(register int j=0;j<4;j++) ch[cnt][j]=0; return cnt; } inline int ExtendNode(register short c,SAM&sam) { register int now=sam.last,nw=CreateNode(mxval[sam.last]+1); for(; now && !ch[now][c]; now=parent[now]) ch[now][c]=nw; if(!now) return parent[nw]=sam.root,sam.last=nw; register int q=ch[now][c]; if(mxval[q] == mxval[now]+1) return parent[nw]=q,sam.last=nw; register int b=CreateNode(mxval[now]+1); for(register int j=0;j<4;j++) ch[b][j]=ch[q][j]; parent[b]=parent[q],parent[q]=parent[nw]=b; for(; now && ch[now][c]==q; now=parent[now]) ch[now][c]=b; return sam.last=nw; } char s[2550505]; int ans,top; char stk[2550505]; void DFSOut(register int now) { fwrite(&stk[1],top,1,stdout),putchar('\n'); ans++; for(register int j=0;j<4;j++) if(ch[now][j]) stk[++top]=GetChar(j),DFSOut(ch[now][j]),stk[top--]=0; } int f[2550505]; bool vis[2550505]; void DFS(register int now) { if(vis[now]) return; vis[now]=true; for(register int j=0;j<4;j++) if(ch[now][j]) DFS(ch[now][j]),((f[now]+=f[ch[now][j]])>=MOD ? f[now]-=MOD : 0); (++f[now]) >= MOD ? f[now]-=MOD : 0; } int main() { int N;scanf("%d",&N); for(register int lp=1;lp<=N;lp++) { int ls;getstr(s,ls); sam[lp].root=sam[lp].last=CreateNode(); for(register int i=1;i<=ls;i++) ExtendNode(MapChar(s[i]),sam[lp]); } for(register int lp=N;lp>=1;lp--) { static int match[4]={0}; if(lp<N) for(register int i=sam[lp].root;i<sam[lp+1].root;i++) for(register int j=0;j<4;j++) if(!ch[i][j]) ch[i][j]=match[j]; for(register int j=0;j<4;j++) if(ch[sam[lp].root][j]) match[j]=ch[sam[lp].root][j]; } int K;scanf("%d",&K); if(K==0) DFS(sam[1].root),printf("%d\n",f[sam[1].root]); else DFSOut(sam[1].root),printf("%d\n",ans); return 0; } |