二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
链接
Luogu P2444
题解
对所有的模版串建立AC自动机，补全Trie图，在Trie图上找环。
注意这里不能到达单词结束的节点，也不能到达所有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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| #include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 1001000;
template <int sigma_size>
struct AC_automaton{
bool vis[MAXN],flag;
bool instack[MAXN];
int f[MAXN],c[MAXN][sigma_size],end[MAXN];
int root,cnt;
AC_automaton(){root=cnt=0;}
void clear(){}
void insert(char *str){
int n = strlen(str),nown = root;
for(int i = 0;i<n;i++){
if(!c[nown][str[i]-'0'])
c[nown][str[i]-'0'] = ++cnt;
nown = c[nown][str[i]-'0'];
}
end[nown] |= 1;
}
void get_fail(){
queue<int> q;
while(!q.empty()) q.pop();
for(int i = 0;i<sigma_size;i++){
if(c[root][i]){
f[c[root][i]] = root;
q.push(c[root][i]);
}
}
while(!q.empty()){
int nown = q.front();q.pop();
for(int i = 0;i<sigma_size;i++){
if(c[nown][i]){
f[c[nown][i]] = c[f[nown]][i];
end[c[nown][i]] |= end[f[c[nown][i]]];
q.push(c[nown][i]);
}
else c[nown][i] = c[f[nown]][i];
}
}
}
bool judge(){
memset(vis,0,sizeof(vis));
memset(instack,0,sizeof(instack));
flag = 0;
for(int i = 0;i<=cnt;i++){
if(!vis[i] && !end[i]) flag |= dfs(i);
if(flag) return true;
}
return false;
}
bool dfs(int x){
instack[x] = vis[x] = 1;
for(int i = 0;i<sigma_size;i++){
int v = c[x][i];
if(end[v]) continue;
if(instack[v] || (!vis[v] && dfs(v)))
return true;
}
instack[x] = 0;
return false;
}
};
AC_automaton<2> AC;
int n;
char s[MAXN];
void init(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%s",s);
AC.insert(s);
}
}
void solve(){
AC.get_fail();
if(AC.judge()){
printf("TAK\n");
}
else{
printf("NIE\n");
}
}
int main(){
init();
solve();
return 0;
}
|