题目描述
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
1.在文本文件WIR.IN中读入病毒代码；
2.判断是否存在一个无限长的安全代码；
3.将结果输出到文件WIR.OUT中。
输入输出格式
输入格式：
在文本文件WIR.IN的第一行包括一个整数n(n\le 2000)(n≤2000)，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
输出格式：
在文本文件WIR.OUT的第一行输出一个单词：
TAK——假如存在这样的代码；
NIE——如果不存在。
输入输出样例
题意：
给n个模式串，问能不能找到一个无限长的文本串，使得模式串没有出现在文本串里。
思路：
看到题目没想法......看了题解
我们会发现正常的AC自动机都是在文本串中去匹配模式串，现在不要模式串出现，那么也就是说希望Trie中被标记为模式串结尾的节点不要出现。我们将这个称为危险标记。而想要无限长的文本串，其实也就是在匹配过程中能否找到这样一个环，使得环上的节点都是安全的。
首先我们还是先建立fail数组，需要注意的是，如果一个节点的fail指针指向的节点是危险的，那么他本身也是危险的。
因为一个节点x的fail指针指向的节点y表示的是以y作为结尾的前缀与以x为结尾的前缀的后缀匹配的最长部分，也就是说根节点到y一定是在根节点到x中出现过的。
然后dfs，用一个数组vis标记路径，一个数组f标记是否访问过。vis在dfs结束后要恢复，是用来判断当前路径是否形成环的。
#include <iostream>
#include <set>
#include <cmath>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
#define inf 0x7f7f7f7f int n;
const int maxn = ; struct Tree{
int fail;//失配指针
int vis[];//子节点位置
int ed;//标记有几个单词以这个节点结尾
}AC[maxn];
string s;
int tot = ; void build(string s)
{
int len = s.length();
int now = ;//字典树当前指针
for(int i = ; i < len; i++){
if(AC[now].vis[s[i] - ''] == ){
AC[now].vis[s[i] - ''] = ++tot;
}
now = AC[now].vis[s[i] - ''];
}
AC[now].ed = ;
} void get_fail()
{
queue<int> que;
for(int i = ; i < ; i++){
if(AC[].vis[i] != ){
AC[AC[].vis[i]].fail = ;
que.push(AC[].vis[i]);
}
}
while(!que.empty()){
int u = que.front();
que.pop();
for(int i = ; i < ; i++){
if(AC[u].vis[i] != ){
AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
if(AC[AC[u].fail].ed){
AC[u].ed = ;
}
que.push(AC[u].vis[i]);
}
else{
AC[u].vis[i] = AC[AC[u].fail].vis[i];
}
}
}
} bool vis[maxn], f[maxn];
void dfs(int rt)
{
vis[rt] = true;
for(int i = ; i < ; i++){
if(vis[AC[rt].vis[i]]){
printf("TAK\n");
exit();
}
else if(!AC[AC[rt].vis[i]].ed && !f[AC[rt].vis[i]]){
f[AC[rt].vis[i]] = true;
dfs(AC[rt].vis[i]);
}
}
vis[rt] = false;
} int main()
{
scanf("%d", &n);
for(int i = ; i < n; i++){
cin>>s;
build(s);
}
AC[].fail = ;
get_fail();
dfs();
printf("NIE\n");
//cout<<s[maxid]<<endl;
//cout<<AC_query(s)<<endl;
return ;
}