BZOJ2938

• 传送门:BZOJ2938

　　我们观察到可以构造出字符串满足题意的充分必要条件是，以病毒代码构造的Trie图有环。
　　
　　让我们考虑命题的证明，充分性是显然的，下证必要性。

　　假设构造出了满足题意的字符串S，那么对于S[i]，其在AC自动机上对应节点及其后缀链接必然是非单词的。很容易发现，遍历了所有对应节点后，下一个节点一定会形成环。
　　
　　Q.E.D

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int maxnode=30005,sigma=2;
struct Trie{
    int tot;
    int ch[maxnode][sigma];
    int val[maxnode];
    int f[maxnode];
    bool danger[maxnode];
    int last[maxnode];  
    bool ins[maxnode];
    bool used[maxnode];
    Trie(){
        tot=1;
        memset(ch,0,sizeof(ch));
        memset(danger,false,sizeof(danger));
        memset(f,0,sizeof(f));
        memset(last,0,sizeof(last));
        memset(ins,false,sizeof(ins));
        memset(used,false,sizeof(used));
    }
    inline int idx(char a){
        return a-'0';
    }
    void Clear(){
        tot=1;
        memset(danger,false,sizeof(danger));
        memset(ch[0],0,sizeof(ch[0]));
        memset(used,false,sizeof(used));
        memset(ins,false,sizeof(ins));
    }
    int newnode(){
        memset(ch[tot],0,sizeof(ch[tot]));
        return tot++;
    }
    void Insert(string s){
        int len=s.length();
        int u=0;
        for(int i=0;i<len;i++){
            if(ch[u][idx(s[i])]==0)
                ch[u][idx(s[i])]=newnode();
            u=ch[u][idx(s[i])];
        }
        danger[u]=true;
    }
    void Build(){
        queue<int> Q;
        while(!Q.empty())
            Q.pop();
        for(int i=0;i<sigma;i++)
            if(ch[0][i]){
                Q.push(ch[0][i]);
                last[ch[0][i]]=f[ch[0][i]]=0;
            }
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=0;i<sigma;i++){
                if(ch[u][i]==0){
                    ch[u][i]=ch[f[u]][i];
                    continue;
                }
                int v=ch[u][i];
                Q.push(v);
                int r=f[u];
                while(r&&ch[r][i]==0)
                    r=f[r];
                f[v]=ch[r][i];
                danger[v]|=danger[f[v]];
            }
        }
    }
    bool HaveRing(int from){
        ins[from]=true;
        for(int i=0;i<sigma;i++){
            if(ins[ch[from][i]])
                return true;
            if(danger[ch[from][i]]||used[ch[from][i]])
                continue;
            used[from]=true;
            if(HaveRing(ch[from][i]))
                return true;
        }
        ins[from]=false;
        return false;
    }
};
Trie Aho_Corasick;
string S;
int n;
void Solve()
{
    Aho_Corasick.Build();
    if(Aho_Corasick.HaveRing(0))
        cout<<"TAK";
    else
        cout<<"NIE";
}
void ReadData()
{
    freopen("BZOJ2938.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>S;
        Aho_Corasick.Insert(S);
    }
}
void Close()
{
    fclose(stdin);
    fclose(stdout);
}
int main()
{
    ReadData();
    Solve();
    Close();
    return 0;
}