[Poi2000]病毒

灰太狼 2021-03-17 14:54 590阅读 0赞

Time Limit: 1 Sec  Memory Limit: 128 MB  
Submit: 993  Solved: 500  
Submit Status Discuss

## Description ##

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

示例：

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

任务：

请写一个程序：

1.  读入病毒代码；
2.  判断是否存在一个无限长的安全代码；
3.  将结果输出

## Input ##

第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。

## Output ##

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

1.  TAK——假如存在这样的代码；
2.  NIE——如果不存在。

## Sample Input ##

3  
01  
11  
00000

## Sample Output ##

NIE

## 思路 ##

AC自动机+拓扑序列；

## 代码实现 ##

#include<cstdio>
     const int maxn=3e4+10;
     int n;
     char ch[maxn];
     int next[maxn][2],fail[maxn],sz=2;
     bool end[maxn];
     void ins(){
         int a;
         scanf("%s",ch);
         for(int i=0,j=0;;i++){
             if(!ch[i]){end[j]=1;break;}
             a=ch[i]-'0';
             if(!next[j][a]) next[j][a]=++sz;
             j=next[j][a];
         }
     }
     int q[maxn],head,tail;
     void build(){
         int a,b;
         head=0,tail=2;
         q[0]=1,q[1]=2;
         while(head<tail){
             a=q[head++];
             if(next[a][0]){
                 b=fail[a];
                 while(!next[b][0]) b=fail[b];
                 fail[next[a][0]]=next[b][0];
                 if(end[next[b][0]]) end[next[a][0]]=1;
                 q[tail++]=next[a][0];
             }
             else next[a][0]=next[fail[a]][0];
             if(next[a][1]){
                 b=fail[a];
                 while(!next[b][1]) b=fail[b];
                 fail[next[a][1]]=next[b][1];
                 if(end[next[b][1]]) end[next[a][1]]=1;
                 q[tail++]=next[a][1];
             }
             else next[a][1]=next[fail[a]][1];
         }
     }
     int tot;
     int point[maxn],nxt[maxn<<1],v[maxn<<1],in[maxn];
     bool vis[maxn];
     void add(int x,int y){tot++,nxt[tot]=point[x],point[x]=tot,v[tot]=y;}
     void dfs(int k){
         vis[k]=1;
         add(k,next[k][0]);in[next[k][0]]++;
         if(!vis[next[k][0]]&&!end[next[k][0]]) dfs(next[k][0]);
         add(k,next[k][1]);in[next[k][1]]++;
         if(!vis[next[k][1]]&&!end[next[k][1]]) dfs(next[k][1]);
     }
     bool f_ring(){
         int cnt=0,a;
         head=tail=0;
         for(int i=0;i<sz;i++) if(!in[i]) q[tail++]=i;
         while(head<tail){
             a=q[head++],cnt++;
             for(int i=point[a];i;i=nxt[i]){
                 in[v[i]]--;
                 if(!in[v[i]]) q[tail++]=v[i];
             }
         }
         return cnt<sz;
     }
     int main(){
         scanf("%d",&n);
         next[0][0]=1,next[0][1]=2;
         for(int i=1;i<=n;i++) ins();
         build();
         dfs(0);
         if(f_ring()) puts("TAK");
         else puts("NIE");
         return 0;
     }