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:
| 1 2 3 4 | 3 01 11 00000 |
Sample Output:
| 1 | NIE |
题解：
好久没有写过AC自动机了，来练练手结果又被卡了很久QAQ
直接对所有病毒串构造AC自动机，然后DFS找是否存在不经过单词节点的环。
代码如下：
| 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 | /* ID: Sunshine_cfbsl PROG: BZOJ2938 LANG: C++ */ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAXL = 30010; int n, ch[MAXL][2], cnt = 1; int q[MAXL], fail[MAXL], head, tail; char s[MAXL]; bool val[MAXL], vis[MAXL], used[MAXL]; inline int read() { int x = 0, f = 1; char ch = getchar(); for(; ch<'0' || ch>'9'; ch=getchar()) if(ch=='-') f=-1; for(; ch>='0'&&ch<='9'; ch=getchar()) x = x*10 + ch-'0'; return x * f; } inline void insert(char s[], int l) { int i, p = 1; for(i = 0; i < l; i++) { if(!ch[p][s[i]-'0']) ch[p][s[i]-'0'] = ++cnt; p = ch[p][s[i]-'0']; } val[p] = true; } inline void getfail() { q[++tail] = 1, fail[0] = 1; while(head < tail) { int i, u = q[++head]; for(i = 0; i < 2; i++) { int v = ch[u][i], k = fail[u]; if(!v) { ch[u][i] = ch[k][i]; continue; } while(!ch[k][i]) k = fail[k]; fail[v] = ch[k][i]; val[v] |= val[ch[k][i]]; q[++tail] = v; } } } bool dfs(int u) { used[u] = true; int i; for(i = 0; i < 2; i++) { if(used[ch[u][i]]) return true; if(vis[ch[u][i]]||val[ch[u][i]]) continue; vis[ch[u][i]] = true; if(dfs(ch[u][i])) return true; } used[u] = false; return false; } int main() { int i; n = read(); ch[0][0] = ch[0][1] = 1; for(i = 1; i <= n; i++) { scanf("%s", s); insert(s, strlen(s)); } getfail(); if(dfs(1)) printf("TAK\n"); else printf("NIE\n"); return 0; } |
