bzoj 2938 [Poi2000]病毒

内容

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

00000

Sample Output

NIE

题解

把010101010放到{011, 11, 00000}的AC自动机里面匹配一下，发现会一直走一个环。

那就在AC自动机上，以父亲到儿子的边和fail的边搞下判个环就可以了。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define N 100010
using namespace std;
int ch[N][2],is_end[N],fail[N],vis[N],root=1,sz=1,n;
char s[N];
void insert(char s[])
{
int len=strlen(s+1),now=root;
for (int i=1;i<=len;now=ch[now][s[i]-'0'],i++)
if (!ch[now][s[i]-'0']) ch[now][s[i]-'0']=++sz;
is_end[now]=1;
}
void make_fail()
{
queue<int>que;
que.push(root);
while(!que.empty())
{
int now=que.front();que.pop();
for (int i=0;i<=1;i++)
if (ch[now][i])
{
int t=fail[now];
while (t && !ch[t][i]) t=fail[t];
if (t && now!=root) fail[ch[now][i]]=ch[t][i];
else fail[ch[now][i]]=root;
que.push(ch[now][i]);
}
}
}
void dfs(int now)
{
if (fail[now]) dfs(fail[now]);
if (!ch[now][0]) ch[now][0]=ch[fail[now]][0];
if (!ch[now][1]) ch[now][1]=ch[fail[now]][1];
is_end[now]+=is_end[fail[now]];
}
void rebuild()
{
for (int i=1;i<=sz;i++)
dfs(i);
}
void finds(int now,int pre)
{
vis[now]=2;
for (int i=0;i<=1;i++)
{
int next=0;
if (ch[now][i])
next=ch[now][i];
else if (fail[now]!=pre)
next=fail[now];
else continue;
if (is_end[next]) continue;
if (!vis[next]) finds(next,now);
else if (vis[next]==2)
{
puts("TAK");
exit(0);
}
}
vis[now]=1;
}
main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%s",s+1),insert(s);
make_fail();
rebuild();
finds(root,root);
puts("NIE");
}