[POI2000]病毒

https://www.luogu.org/problemnew/show/P2444

https://www.lydsy.com/JudgeOnline/problem.php?id=2938

题解：AC自动机

AC自动机是一种多模字符串匹配算法。构造 Trie 树 后，在模式串末尾一位的结点作上标记。平常的 AC自动机 是尽量能多接触到这些标记，使总值最大。本题倒是有点奇葩，要构造一个可行的无限长文本串，使没有任何子串为给出模式串中的一个。也就是说，我们需要让平常 AC自动机 的查询操作，尽量避免标记，能用失配指针跳转就跳转。

因为要有无限长的可行串，根据 AC自动机 的原理，我们可以将结点连接到儿子的边当作一条单向边，同时失配指针也当作一条单向边，如果存在一个环，且环上没有任何危险标记（即病毒代码段末尾一位的结点专门作的编号），此时 AC自动机 能一直在环上匹配，并且永远也不会得到为模式串的一个子串，就像程序中的死循环一样。这个找环我们可以通过 dfs 来实现。

注意事项

1 . 我们需要建立两个布尔数组，其中一个布尔数组记录每个节点在当前 dfs 走的路径上有没有被选中，另一个布尔数组记录每个节点历史上有没有被访问过。如果当前路径形成回路，就找到环了，应该还是比较好实现的。

2 . 避免危险标记，也就是说如果下一个结点拥有危险标记，就不走那个结点。

3 . 在构造失配指针时，一个很明显的优化是：如果一个结点拥有了失配指针，它指向的结点如果有危险标记，自己必然也危险，因为它到根结点形成的串是自己到根节点的后缀。

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=3e5+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
char str[N];
struct Aho_Corasick_Automaton{
    int trie[N][2],val[N],fail[N],last[N],nodenum,vis[N],pre[N],d[N];
    void clear(){
        memset(trie,0,sizeof(trie));
        memset(val,0,sizeof(val));
        memset(vis,0,sizeof(vis));
        memset(pre,0,sizeof(pre));
        memset(fail,0,sizeof(fail));
        memset(last,0,sizeof(last));
        memset(d,0,sizeof(d));
        nodenum=0;
    }
    void insert(char * str){
        int len=strlen(str),pos=0;
        for(int i=0;i<len;i++){
            int ch=str[i]-'0';
            if(trie[pos][ch]==0)trie[pos][ch]=++nodenum;
            pos=trie[pos][ch];
        }
        val[pos]++;
        d[pos]=1;
    }
    void GetFail(){
        queue<int>Q;
        Q.push(0);
        while(!Q.empty()){
            int u=Q.front(),k=fail[u];
            Q.pop();
            for(int ch=0;ch<=1;ch++){
                int v=trie[u][ch];
                if (!v){trie[u][ch]=trie[k][ch];continue;}
                Q.push(v);
                fail[v]=u?trie[k][ch]:0;
                if(u&&d[trie[k][ch]])d[v]=1;
                last[v]=val[fail[v]]?fail[v]:last[fail[v]];
            }
        }
    }
    bool DFS(int u){ // 通过搜索寻找有没有环
        pre[u] = 1; // 作下路径标记
        for(int i = 0 ; i <= 1 ; i++){
            int v=trie[u][i];
            if(pre[v]){ // 根据路径标记判断是否拥有环
                return true;
            }else if(!d[v] && !vis[v]){
                // 只有下一位不为危险结点并且有可能成环，才递归搜索
                vis[v] = 1; // 下一个结点已经被搜索过了
                if(DFS(v))return true;
            }
        }
        pre[u] = 0; // 抹除路径标记
        return false;
    }
}AC;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    while(~scanf("%d",&n)){
        AC.clear();
        for(int i=1;i<=n;i++){
            scanf("%s",str);
            AC.insert(str);
        }
        AC.GetFail();
        cout<<(AC.DFS(0)?"TAK":"NIE")<<endl;
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}