[AC自动机][dfs] 洛谷 P2444 病毒

题目描述

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。

任务：

请写一个程序：

1.在文本文件WIR.IN中读入病毒代码；

2.判断是否存在一个无限长的安全代码；

3.将结果输出到文件WIR.OUT中。

输入输出格式

输入格式：

在文本文件WIR.IN的第一行包括一个整数n

输出格式：

在文本文件WIR.OUT的第一行输出一个单词：

TAK——假如存在这样的代码；

NIE——如果不存在。

输入输出样例

输入样例#1：

输出样例#1：

NIE

题解

题目大意是要求是否有没有被匹配的无限长代码
这题有点奇怪，求的无限长代码
那么就是要一直失配，那么可以将fail边(失配边)当成原树边来做
这样的话，其实就是要在trie树上求没有匹配的字串的一个环，dfs做

代码

 1 #include <cstdio> 
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <queue>
 6 using namespace std;
 7 bool vis[30010],g[30010];
 8 char ch[30010];
 9 int n,cnt,f[30010][4];
10 queue<int> Q;
11 void insert(char ch[],int len)
12 {
13     int p=0;
14     for (int i=1;i<=len;i++)
15         if (f[p][ch[i]-'0']==0) f[p][ch[i]-'0']=++cnt,p=cnt;
16         else p=f[p][ch[i]-'0'];
17     f[p][2]=true;
18 }
19 void getfail()
20 {
21     if (f[0][0]>0) Q.push(f[0][0]);
22     if (f[0][1]>0) Q.push(f[0][1]);
23     while (!Q.empty())
24     {
25         int u=Q.front(); Q.pop();
26         for (int i=0;i<=1;i++)
27             if (f[u][i]>0)
28             {
29                 Q.push(f[u][i]);
30                 int v=f[u][3];
31                 while (v&&f[v][i]<=0) v=f[v][3];
32                 if (f[v][i]<=0) f[f[u][i]][3]=0;
33                 else
34                 {
35                     f[f[u][i]][3]=f[v][i];
36                     if (f[f[v][i]][2]) f[f[u][i]][2]=true;
37                 }
38             }
39             else f[u][i]=f[f[u][3]][i];
40     }
41 }
42 void dfs(int x)
43 {
44     vis[x]=true;
45     for (int i=0;i<=1;i++)
46         if (vis[f[x][i]]) { printf("TAK"); exit(0); }
47         else
48             if (!f[f[x][i]][2]&&!g[f[x][i]]) g[f[x][i]]=true,dfs(f[x][i]);
49     vis[x]=false;
50 }
51 int main()
52 {
53     scanf("%d",&n);
54     for (int i=1;i<=n;i++) scanf("%s",ch+1),insert(ch,strlen(ch+1));
55     getfail();
56     dfs(0);
57     printf("NIE");
58 }