【题目描述】

二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。

示例:例如如果${011, 11, 00000}$为病毒代码段,那么一个可能的无限长安全代码就是$010101\cdots$。如果${01, 11, 000000}$为病毒代码段,那么就不存在一个无限长的安全代码。

请写一个程序,读入病毒代码,判断是否存在一个无限长的安全代码,将结果输出。

【输入格式】

第一行包括一个整数$n$,表示病毒代码段的数目;
以下的$n$行,每一行都包括一个非空的$01$字符串——就是一个病毒代码段。

【输出格式】
假如存在这样的代码,则输出 TAK,否则输出 NIE。

题解

由于是AC自动机专题 所以我们不妨考虑一下怎么用AC自动机解决

显而易见 这个无限长的$01$串应该是有循环节的

把$n$个危险串插入AC自动机 在结束节点打标记

那么当你在AC自动机上对这个$01$循环串做匹配的时候,当前指针走的应该也是循环,并且 沿途经过的节点 以及 每个经过节点到根的fail链上 都没有结束节点

因为用AC自动机做匹配的时候不是走到每个节点都要跳fail 如果跳到有结束tag的就(文章包含单词数)+1吗 而这里我们希望它为0

所以我们把所有 有结束tag的节点 及 这个节点到根的fail链上有结束节点 的节点删掉(设为不可用)

然后在剩下的节点构成的这个不完整的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
#include <bits/stdc++.h>
using namespace std;

int n, len;
char s[100005];

int ch[100005][2], fail[100005], tot;
bool tag[100005];

inline void insert(char *str, int l) {
int x = 0;
for (int i = 1; i <= l; i++) {
if (!ch[x][str[i] - '0']) {
ch[x][str[i] - '0'] = ++tot;
}
x = ch[x][str[i] - '0'];
}
tag[x] = 1;
}

queue<int> q;

inline void getfail() {
for (int i = 0; i < 2; i++) if (ch[0][i]) q.push(ch[0][i]);
while (!q.empty()) {
int x = q.front(); q.pop();
tag[x] |= tag[fail[x]];
for (int i = 0; i < 2; i++) {
if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
else ch[x][i] = ch[fail[x]][i];
}
}
}

int dfn[30005], low[30005], stk[30005], tme, top;
bool vis[30005], flag;

void tarjan(int x) {
dfn[x] = low[x] = ++tme;
vis[x] = 1;
stk[++top] = x;
for (int i = 0; i < 2; i++) {
if (tag[ch[x][i]]) continue;
int y = ch[x][i];
if (x == y) flag = 1;
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (vis[y]) {
low[x] = min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x]) {
int now = 0, totot = 0;
do {
now = stk[top--];
vis[now] = 0;
totot++;
} while (now != x);
if (totot > 1) flag = 1;
}
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
memset(s, 0, sizeof(s));
scanf("%s", s+1); len = strlen(s+1);
insert(s, len);
}
getfail();
flag = 0;
tarjan(0);
if (flag) puts("TAK");
else puts("NIE");
return 0;
}

评论