题目描述
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
输入
第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
输出
你应在在第一行输出一个单词：
样例
样例输入
3
01
11
00000
样例输出
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#define rint register int
using namespace std;
char ch[30004];
int n;
int trie[30004][2];
int cnt=1,fail[30004];
bool endd[30004],vis[30004];
bool ans=false,failed[30004];
inline void insert(char *str)
{
int len=strlen(str),p=1;
for(rint i=0;i<len;++i)
{
int l=str[i]-‘0‘;
if(!trie[p][l])
trie[p][l]=++cnt;
p=trie[p][l];
}
endd[p]=true;
}
inline void get_fail()
{
queue <int>q;
q.push(1);
fail[1]=0;
trie[0][0]=trie[0][1]=1;
while(!q.empty())
{
int l=q.front();q.pop();
for(rint i=0;i<2;++i)
{
if(trie[l][i])
{
fail[trie[l][i]]=trie[fail[l]][i];
if(endd[fail[trie[l][i]]])
endd[trie[l][i]]=true;//注意这两句话，没加毁人生QAQ
q.push(trie[l][i]);
}
else trie[l][i]=trie[fail[l]][i];
}
}
}
inline void dfs(int u)
{
vis[u]=1;
for(int i=0;i<=1;i++)
{
if(vis[trie[u][i]])
{
ans=true;
return ;
}
else if(!failed[trie[u][i]]&&!endd[trie[u][i]])
{
failed[trie[u][i]]=1;
dfs(trie[u][i]);
}
}
vis[u]=0;
return ;
}
int main()
{
// freopen("wir213.in","r",stdin);
scanf("%d",&n);
for(rint i=1;i<=n;++i)
{
scanf("%s",ch);
insert(ch);
}
get_fail();
// for(rint i=1;i<=cnt;++i)cout<<fail[i]<<endl;
dfs(1);
if(ans)cout<<"TAK"<<endl;
else cout<<"NIE"<<endl;
return 0;
}
完结撒花～
原文：https://www.cnblogs.com/xingmi-weiyouni/p/11082103.html