本文转载自：

题目大意：

有N个确定的二进制串是病毒的代码。当某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

n≤2000 

所有病毒代码段的总长度不超过30000

题解：

将所有的病毒代码构建一个AC自动机， 

如果存在一个可行解，必定它在trie树中，从根节点开始走，不会碰到所有病毒的末尾节点（即不可行的点）。 
而一个点，显然它的fail边连的点不可行，则这个点也必定是不可行的。 
那么我们可以从trie的根节点进行dfs， 
注意不走危险节点，不走历史访问过而已经不在栈中的节点 
记录每个节点在当前 dfs 走的路径上有没有被选中，注意要保证路径上的点不存在不可行节点 
当路径中出现环，则有解

代码：

#include
     
       #define N 233333 using namespace std;   int n,num,next[N][2],fail[N],end[N],vis[N],rp[N];   char s[N]; void insert(char *s) {
          int len=strlen(s);      int u=0;      for (int i=0; i
Q;     for (int i=0; i<=1; i++)            if (next[0][i]) Q.push(next[0][i]);       while (!Q.empty())             {
                int u=Q.front();               Q.pop();                 for (int i=0; i<=1; i++)                     if (!next[u][i])                       next[u][i]=next[fail[u]][i];                       else {
                           end[next[u][i]]|=end[next[fail[u]][i]];                              fail[next[u][i]]=next[fail[u]][i];                              Q.push(next[u][i]);                          }           }       }   bool dfs(int dep)   {
     vis[dep]=rp[dep]=1;      for(int i=0; i<=1; i++)          {
           if (rp[next[dep][i]]) return 1;            if (!end[next[dep][i]] && !vis[next[dep][i]] && dfs(next[dep][i])) return 1;          }    rp[dep]=0;      return 0;   }   int main()   {
     scanf("%d",&n);      for (int i=1; i<=n; i++)        {
              scanf("%s",s);             insert(s);          }      build();      if (dfs(0)) printf("TAK");           else printf("NIE");    return 0;   }