当前位置：首页 > news >正文

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

news 来源：原创 2024/4/29 15:36:20

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

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 #define N (100000+100)
 6 using namespace std;
 7 int Son[N][27],Fail[N],End[N],Ind[N];
 8 int n,sz,head[N],num_edge;
 9 bool vis[N],flag;
10 char s[N];
11 queue<int>q;
12 
13 void Insert(char s[])
14 {
15     int now=0,len=strlen(s);
16     for (int i=0; i<len; ++i)
17     {
18         int x=s[i]-'0';
19         if (!Son[now][x]) Son[now][x]=++sz;
20         now=Son[now][x];
21     }
22     ++End[now];
23 }
24 
25 void Build_Fail()
26 {
27     for (int i=0; i<=1; ++i)
28         if (Son[0][i])
29             q.push(Son[0][i]);
30     while (!q.empty())
31     {
32         int now=q.front();
33         q.pop();
34         for (int i=0; i<=1; ++i)
35         {
36             if (!Son[now][i])
37             {
38                 Son[now][i]=Son[Fail[now]][i];
39                 continue;
40             }
41             Fail[Son[now][i]]=Son[Fail[now]][i];
42             if (End[Fail[Son[now][i]]]) End[Son[now][i]]++;
43             //因为fail指针指向的点代表的字符串一定是当前字符串的一个最长后缀
44             //若后缀都是病毒了，那他本身一定也是病毒了
45             q.push(Son[now][i]);
46         }
47     }
48 }
49 
50 int ins[N],used[N];
51 bool Dfs(int x)
52 {
53     ins[x]=1;
54     for(int i=0; i<2; i++)
55     {
56         int v=Son[x][i];
57         if(ins[v])return 1;
58         if(used[v]||End[v])continue;
59         used[v]=1;
60         if(Dfs(v))return 1;
61     }
62     ins[x]=0;
63     return 0;
64 }
65 
66 int main()
67 {
68     scanf("%d",&n);
69     for (int i=1; i<=n; ++i)
70         scanf("%s",s),Insert(s);
71     Build_Fail();
72     if(Dfs(0))puts("TAK");
73     else puts("NIE");
74 }