首页 > 代码库 > Hnu 10104 病毒 (AC自动机+dfs)

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

2024-07-20 22:46:01   227人阅读

病毒
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
3
01
11
00000
Sample Output
NIE
Problem Source
SDOI
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;
}


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


联系
我们