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

时间：2024-04-06 22:35:48

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

Solution

QvQ现在才理解AC自动机buildfail的时候继承儿子其实就相当于把trie树补成trie图
对于这个题只需要建好trie图，然后在trie图上找一个环
为什么呢？因为我们如果拿一个安全代码在自动机上跑
一定会不停的跑而到不了单词的结束点，这就要求必须有个环
而且这个环要求必须经过根节点，且不经过一些限制节点
限制节点包括单词的结束节点，还有若一个点的fail指向的点是限制节点
那么这个点也是限制节点。
因为fail指向的是当前串的最长后缀，
fail指向的后缀都是病毒了，那当前串本身一定也是病毒了

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #define N (100000+100)

 using namespace std;

 int Son[N][],Fail[N],End[N],Ind[N];

 int n,sz,head[N],num_edge;

 bool vis[N],flag;

 char s[N];

 queue<int>q;

 void Insert(char s[])

 {

     int now=,len=strlen(s);

     for (int i=; i<len; ++i)

     {

         int x=s[i]-'';

         if (!Son[now][x]) Son[now][x]=++sz;

         now=Son[now][x];

     }

     ++End[now];

 }

 void Build_Fail()

 {

     for (int i=; i<=; ++i)

         if (Son[][i])

             q.push(Son[][i]);

     while (!q.empty())

     {

         int now=q.front();

         q.pop();

         for (int i=; i<=; ++i)

         {

             if (!Son[now][i])

             {

                 Son[now][i]=Son[Fail[now]][i];

                 continue;

             }

             Fail[Son[now][i]]=Son[Fail[now]][i];

             if (End[Fail[Son[now][i]]]) End[Son[now][i]]++;

             //因为fail指针指向的点代表的字符串一定是当前字符串的一个最长后缀

             //若后缀都是病毒了，那他本身一定也是病毒了

             q.push(Son[now][i]);

         }

     }

 }

 int ins[N],used[N];

 bool Dfs(int x)

 {

     ins[x]=;

     for(int i=; i<; i++)

     {

         int v=Son[x][i];

         if(ins[v])return ;

         if(used[v]||End[v])continue;

         used[v]=;

         if(Dfs(v))return ;

     }

     ins[x]=;

     return ;

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; ++i)

         scanf("%s",s),Insert(s);

     Build_Fail();

     if(Dfs())puts("TAK");

     else puts("NIE");

 }

相关文章