http://www.elijahqi.win/archives/2880 Description 二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我
http://www.elijahqi.win/archives/2880
Description
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
l 读入病毒代码；
l 判断是否存在一个无限长的安全代码；
l 将结果输出
Input
第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
Output
你应在在文本文件WIN.OUT的第一行输出一个单词：
l TAK——假如存在这样的代码；
l NIE——如果不存在。
Sample Input
3
01
11
00000
Sample Output
NIE
HINT
Source
建出AC自动机拓扑排序判环即可
#include<queue>#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 30030
using namespace std;
int trans[N][2],fail[N],cnt=1,n,in[N];
char s[N]; bool end[N];
inline void insert1(char s[]){
int len=strlen(s+1);int p=1;
for (int i=1,nxt;i<=len;++i) {
if (!trans[p][s[i]-'0']) trans[p][s[i]-'0']=nxt=++cnt;
else nxt=trans[p][s[i]-'0'];p=nxt;
}end[p]=1;
}
inline void buildAC(){
queue<int>q;q.push(1);trans[0][0]=trans[0][1]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<=1;++i){
if (trans[x][i])fail[trans[x][i]]=trans[fail[x]][i],q.push(trans[x][i]);else
{trans[x][i]=trans[fail[x]][i];continue;}end[trans[x][i]]|=end[fail[trans[x][i]]];
}
}
}
int main(){
freopen("bzoj2938.in","r",stdin);
scanf("%d",&n);queue<int>q;
for (int i=1;i<=n;++i) scanf("%s",s+1),insert1(s);buildAC();
for (int i=0;i<=cnt;++i) {
if(end[i]) continue;
for (int j=0;j<=1;++j) if (!end[trans[i][j]])++in[trans[i][j]];
}for (int i=0;i<=cnt;++i) if (!in[i]&&!end[i]) q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
for (int i=0;i<=1;++i){
if(end[trans[x][i]]) continue;
if(!--in[trans[x][i]]) q.push(trans[x][i]);
}
}for (int i=0;i<=cnt;++i) if (in[i]&&i!=1) {puts("TAK");return 0;}puts("NIE");
return 0;
}