沃通(WoSign)数字证书
EmailGoogleTwitterFacebook

Hnu 10104 病毒 (AC自动机+dfs)

病毒
Time Limit:  1000ms,  Special Time Limit: 2500ms,  Memory Limit: 32768KB
Total submit users: 41,  Accepted users:  23
Problem 10104 :  No special judgement
Problem description
二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。 例如如果{011, 11, 00000}为病毒代码段,那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段,那么就不存在一个无限长的安全代码。 任务: 请写一个程序: 读入病毒代码; 判断是否存在一个无限长的安全代码; 将结果输出。
Input
第一行包括一个整数n,表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
Output
输出一个单词: TAK——假如存在这样的代码; NIE——如果不存在
Sample Input
Sample Output
NIE
Problem Source
Submit Discuss Judge Status Problems Ranklist

题目链接

http://acm.hnu.cn/online/?action=problem&type=show&id=10104

思路分析:

仔细分析就会发现,如果在ac自动机上存在一个环,且这个环上没有单词的末尾节点,那么就可以。

为什么连单词的末尾节点也不行。

因为ac自动机上的next指向了的是与它具有最长后缀等于前缀的,如果这个时候后缀指向了单词末尾节点的前面,也就意味着有一个前缀在这个末尾节点的前面,那么这个环总会出现一个单词节点。

所以在dfs的时候,要避开一切的单词末尾节点。

至于dfs的时候,我们要判断的也是一条连续的链上的环,所以在深搜的时候用1去标记,然后回溯的时候,标记成另外一个。

然后没有标记的为0.

这样就可以找到链上成环的节点了。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 105
#define maxn 30005
using namespace std;
typedef long long ll;
const int mod = 100000;

const char tab = '0';
const int max_next = 2;

int next[maxn][max_next],fail[maxn],num[maxn],siz;

int newnode()
{
for(int i=0;i<max_next;i++)
next[siz][i]=0;
fail[siz]=num[siz]=0;
return siz++;
}
void init()
{
siz=0;
newnode();
}
void Insert(char *s,int len)
{
int p=0;
for(int i=0;i<len;i++)
{
int &x=next[p][s[i]-tab];
p=x?x:x=newnode();
}
num[p]++;
}

void acbuild()
{
queue<int>Q;
Q.push(0);
while(!Q.empty())
{
int temp=Q.front();
Q.pop();
for(int i=0;i<max_next;i++)
{
int v=next[temp][i];
if(v==0)next[temp][i]=next[fail[temp]][i];
else Q.push(v);
if(temp!=0)fail[v]=next[fail[temp]][i];
if(num[next[fail[temp]][i]])num[next[temp][i]]++;
}
}
}
int vis[maxn];
bool dfs(int now)
{
vis[now]=1;
for(int j=0;j<max_next;j++)
{
if(num[next[now][j]])continue;
if(vis[next[now][j]]==1)return true;
if(vis[next[now][j]]==0 && dfs(next[now][j]))return true;
}
vis[now]=-1;
return false;
}

char word[30005];
int main()
{
int n,L;
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",word);
Insert(word,strlen(word));
}
acbuild();
memset(vis,0,sizeof vis);
bool ans=false;
for(int i=0;i<siz;i++)
if(!vis[i] && dfs(i))
{
ans=true;
break;
}
acdebug();
if(ans)puts("TAK\n");
else puts("NIE\n");
}
return 0;
}

发表评论