【题目描述】
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：例如如果 ({011, 11, 00000}) 为病毒代码段，那么一个可能的无限长安全代码就是 (010101cdots)。如果 ({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一下也行
注意特判一下自环
【代码】
#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;
}