bzoj 2938 [Poi2000]病毒
Description
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
l 读入病毒代码；
l 判断是否存在一个无限长的安全代码；
l 将结果输出
Input
第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
Output
你应在在文本文件WIN.OUT的第一行输出一个单词：
l TAK——假如存在这样的代码；
l NIE——如果不存在。
Sample Input
3
01
11
00000
Sample Output
NIE
题解
把010101010放到{011, 11, 00000}的AC自动机里面匹配一下，发现会一直走一个环。
那就在AC自动机上，以父亲到儿子的边和fail的边搞下判个环就可以了。
|
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 |
#include <cstdio> #include <cstring> #include <cstdlib> #include <queue> #define N 100010 using namespace std; int ch[N][2],is_end[N],fail[N],vis[N],root=1,sz=1,n; char s[N]; void insert(char s[]) { int len=strlen(s+1),now=root; for (int i=1;i<=len;now=ch[now][s[i]-'0'],i++) if (!ch[now][s[i]-'0']) ch[now][s[i]-'0']=++sz; is_end[now]=1; } void make_fail() { queue<int>que; que.push(root); while(!que.empty()) { int now=que.front();que.pop(); for (int i=0;i<=1;i++) if (ch[now][i]) { int t=fail[now]; while (t && !ch[t][i]) t=fail[t]; if (t && now!=root) fail[ch[now][i]]=ch[t][i]; else fail[ch[now][i]]=root; que.push(ch[now][i]); } } } void dfs(int now) { if (fail[now]) dfs(fail[now]); if (!ch[now][0]) ch[now][0]=ch[fail[now]][0]; if (!ch[now][1]) ch[now][1]=ch[fail[now]][1]; is_end[now]+=is_end[fail[now]]; } void rebuild() { for (int i=1;i<=sz;i++) dfs(i); } void finds(int now,int pre) { vis[now]=2; for (int i=0;i<=1;i++) { int next=0; if (ch[now][i]) next=ch[now][i]; else if (fail[now]!=pre) next=fail[now]; else continue; if (is_end[next]) continue; if (!vis[next]) finds(next,now); else if (vis[next]==2) { puts("TAK"); exit(0); } } vis[now]=1; } main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%s",s+1),insert(s); make_fail(); rebuild(); finds(root,root); puts("NIE"); } |