二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。
示例:
例如如果{011, 11, 00000}为病毒代码段,那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段,那么就不存在一个无限长的安全代码。
任务:
请写一个程序:
l 读入病毒代码;
l 判断是否存在一个无限长的安全代码;
l 将结果输出
第一行包括一个整数n,表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
你应在在文本文件WIN.OUT的第一行输出一个单词:
l TAK——假如存在这样的代码;
l NIE——如果不存在。
1 #include<cmath>
2 #include<queue>
3 #include<cstdio>
4 #include<cstring>
5 #include<cstdlib>
6 #include<iostream>
7 #include<algorithm>
8 using namespace std;
9 struct tree
10 {
11 int fail;
12 int vis[3];
13 bool end;
14 }a[30001];
15 int cnt;
16 int n;
17 int num;
18 char s[30001];
19 bool f[30001];
20 bool v[30001];
21 void build(char *s)
22 {
23 int l=strlen(s);
24 int now=0;
25 for(int i=0;i<l;i++)
26 {
27 int x=(s[i]-‘0‘);
28 if(a[now].vis[x]==0)
29 {
30 a[now].vis[x]=++cnt;
31 }
32 now=a[now].vis[x];
33 }
34 a[now].end=true;
35 }
36 void bfs()
37 {
38 queue<int>q;
39 for(int i=0;i<2;i++)
40 {
41 if(a[0].vis[i]!=0)
42 {
43 a[a[0].vis[i]].fail=0;
44 q.push(a[0].vis[i]);
45 }
46 }
47 while(!q.empty())
48 {
49 int now=q.front();
50 q.pop();
51 for(int i=0;i<2;i++)
52 {
53 if(a[now].vis[i]!=0)
54 {
55 a[a[now].vis[i]].fail=a[a[now].fail].vis[i];
56 q.push(a[now].vis[i]);
57 if(a[a[a[now].fail].vis[i]].end)
58 {
59 a[a[now].vis[i]].end=true;
60 }
61 }
62 else
63 {
64 a[now].vis[i]=a[a[now].fail].vis[i];
65 }
66 }
67 }
68 }
69 void dfs(int d)
70 {
71 v[d]=true;
72 for(int i=0;i<2;i++)
73 {
74 if(v[a[d].vis[i]])
75 {
76 printf("TAK");
77 exit(0);
78 }
79 else if(!a[a[d].vis[i]].end&&!f[a[d].vis[i]])
80 {
81 f[a[d].vis[i]]=true;
82 dfs(a[d].vis[i]);
83 }
84 }
85 v[d]=false;
86 }
87 int main()
88 {
89 scanf("%d",&n);
90 for(int i=1;i<=n;i++)
91 {
92 scanf("%s",&s);
93 build(s);
94 }
95 a[0].fail=0;
96 bfs();
97 dfs(0);
98 printf("NIE");
99 return 0;
100 }