BZOJ 2938: [Poi2000]病毒

2938: [Poi2000]病毒

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 693  Solved: 360
[Submit][Status][Discuss]

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

HINT

Source

[Submit][Status][Discuss]

在AC自动机上找不经过dangerous点的环。

 #include <cstdio>

 int tail = ;
 int dang[];
 int fail[];
 int next[][];

 inline void insert(char *s)
 {
     int t = ; 

     for (; *s; ++s)
     {
         int c = *s - '';

         if (next[t][c] == )
             next[t][c] = ++tail;

         t = next[t][c];
     }

     dang[t] = true;    //dangerous node
 }

 inline void preworkFail(void)
 {
     static int que[], l, r;

     fail[que[l = ] = r = ] = ;

     while (l != r)
     {
         int u = que[l++];

         for (int i = ; i < ; ++i)
         {
             if (next[u][i] == )
                 next[u][i] = next[fail[u]][i];
             else
             {
                 int t = fail[u];

                 while (next[t][i] == )
                     t = fail[t];

                 fail[next[u][i]] = next[t][i];

                 if (dang[next[t][i]])
                     dang[next[u][i]] = true;

                 que[r++] = next[u][i];
             }
         }
     }
 }

 bool vis[];
 bool ins[];

 bool findCircle(int u)
 {
     ins[u] = true;

     for (int i = , v; i < ; ++i)
         if (v = next[u][i])
         {
             if (ins[v])return true;
             if (vis[v] || dang[v])continue;
             if (findCircle(v))return true;
         }

     vis[u] = true;
     ins[u] = false;

     return false;
 }

 signed main(void)
 {
     static int n;
     static char str[];

     scanf("%d", &n);

     next[][] = next[][] = ;

     for (int i = ; i <= n; ++i)
         scanf("%s", str), insert(str);

     preworkFail();

     puts(findCircle() ? "TAK" : "NIE");
 }

@Author: YouSiki