BZOJ2938: [Poi2000]病毒(AC自动机)

时间:2022-01-29 04:27:03

2938: [Poi2000]病毒

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1678  Solved: 849
[Submit][Status][Discuss]

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

思路:建立AC自动机,构fail指针,然后如果在避开单词End的情况下存在环,说明可以无限下去。 tarjan求无向图环的时候需要一个队列维护,以免横边,这里也是。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int ch[maxn][],End[maxn],q[maxn],fail[maxn];
int cnt,Flag,head,tail,vis[maxn],inq[maxn]; char c[maxn];
void insert()
{
int L=strlen(c+),Now=;
rep(i,,L) {
if(!ch[Now][c[i]-'']) ch[Now][c[i]-'']=++cnt;
Now=ch[Now][c[i]-''];
}
End[Now]=;
}
void buildfail()
{
rep(i,,) if(ch[][i]) q[++head]=ch[][i];
while(tail<head){
int Now=q[++tail];
rep(i,,){
if(ch[Now][i]){
fail[ch[Now][i]]=ch[fail[Now]][i];
q[++head]=ch[Now][i];
End[ch[Now][i]]|=End[fail[ch[Now][i]]];
}
else ch[Now][i]=ch[fail[Now]][i];
}
}
}
void dfs(int Now)
{
if(Flag||vis[Now]) return ;
if(inq[Now]){ Flag=true; return ;}
inq[Now]=;
if(!End[ch[Now][]]) dfs(ch[Now][]);
if(!End[ch[Now][]]) dfs(ch[Now][]);
vis[Now]=; inq[Now]=;
}
int main()
{
int N; scanf("%d",&N);
rep(i,,N){
scanf("%s",c+);
insert();
}
buildfail();
dfs();
if(Flag) puts("TAK");
else puts("NIE");
return ;
}