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 ;

}

相关文章