Description
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
l 读入病毒代码；
l 判断是否存在一个无限长的安全代码；
l 将结果输出
第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
Output
你应在在文本文件WIN.OUT的第一行输出一个单词：
l TAK——假如存在这样的代码；
l NIE——如果不存在。
3
01
11
00000
Sample Output
NIE
HINT
Source
Solution
首先，一定存在一种答案是无限循环的，如果不是无限循环的话，我们可以不断重复这个串的前30000个字符来变得无限循环。
建立一波AC自动机~~~
然后发现 这其实是在自动机上瞎跑，然后跑的还有套路：跑出来个环且不经过end节点。
做法出来了：AC自动机建立+删点+判是否存在一个从root能到的环。
还有注意这题如果end[fail[now]]=true 我们需要强行把end[now]设为true，因为fail[now]是now的一个后缀~~
Code
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
| #include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 30009;
bool ed[maxn], ins[maxn];
char str[maxn];
int rt, n, tot, go[maxn][2], fail[maxn];
queue<int> Q;
bool check(int now) {
ed[now] = true;
ins[now] = true;
for (int i = 0; i < 2; ++i) {
int to = go[now][i];
if (ins[to]) return true;
if (ed[to]) continue;
if (check(to)) return true;
}
ins[now] = false;
return false;
}
int main() {
int now;
rt = ++tot;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%s", str);
now = rt;
for (int j = 0; str[j]; ++j) {
if (go[now][str[j] - '0'] == 0) go[now][str[j] - '0'] = ++tot;
now = go[now][str[j] - '0'];
}
ed[now] = true;
}
for (int k = 0; k < 2; ++k) {
if (go[rt][k]) {
Q.push(go[rt][k]);
fail[go[rt][k]] = rt;
} else go[rt][k] = rt;
}
while (!Q.empty()) {
now = Q.front(); Q.pop();
ed[now] |= ed[fail[now]];
for (int k = 0; k < 2; ++k) {
if (go[now][k]) {
Q.push(go[now][k]);
fail[go[now][k]] = go[fail[now]][k];
} else go[now][k] = go[fail[now]][k];
}
}
if (check(rt)) puts("TAK");
else puts("NIE");
}
|