2774: Poi2000 病毒
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 5 Solved: 4
[Submit][Status][Web Board]
Description
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。
如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段
试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
读入病毒代码,判断是否存在一个无限长的安全代码；
如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段
试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
读入病毒代码,判断是否存在一个无限长的安全代码；
Input
第一行包括一个整数n，表示病毒代码段的数目。
以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
Output
输出一个单词：
TAK——假如存在这样的代码；
NIE——如果不存在。
TAK——假如存在这样的代码；
NIE——如果不存在。
Sample Input
3
01
11
00000
Sample Output
NIE
HINT
Source
题解：
首先我们把所有串建一个AC自动机
方便起见我们直接把fail指针合并到子结点
如果一个串能无限长,也就是说它可以在AC自动机上一直进行匹配但就是匹配不上
也就是说匹配指针不能走到val为1的结点,设这个点为x
即root..x是一个病毒串
那么fail指针指向x的y也不能走
因为root..x是root..y的一个后缀
处理出来判断有向图是否有环
dfs即可
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 30001
using namespace std;
int n,tot;
char s[maxn];
int sum[maxn],son[maxn][],lis[maxn],fai[maxn];
int ins[maxn],vis[maxn];
void insert()
{
int p=;
scanf("%s",s+);
for (int i=; s[i]; p=son[p][s[i]-''],i++) if (!son[p][s[i]-'']) son[p][s[i]-'']=++tot;
sum[p]=;
}
void failed()
{
int head=,tail=; lis[]=; fai[]=-;
while (head<tail)
{
int x=lis[++head];
for (int i=; i<=; i++)
{
int v=son[x][i];
if (!v)
{
son[x][i]=son[fai[x]][i];
continue;
}
lis[++tail]=v;
int p=fai[x];
while (p!=- && !son[p][i]) p=fai[p];
if (p==-) fai[v]=;
else
fai[v]=son[p][i],sum[v]|=sum[son[p][i]]; }
}
}
bool dfs(int x)
{
ins[x]=;
for (int i=; i<; i++)
{
int v=son[x][i];
if (ins[v]) return ;
if (vis[v] || sum[v]) continue;
vis[v]=;
if (dfs(v)) return ;
}
ins[x]=;
return ;
}
int main()
{
cin>>n; tot=; memset(son,,sizeof(son));
for (int i=; i<=n; i++) insert();
failed();
if (dfs()==) cout<<"TAK"<<endl; else cout<<"NIE"<<endl;
}