BZOJ-2938: [Poi2000]病毒

Description

给你n个01序列p，问能否找到一个无限长的01序列，使得该序列不含有任何一个子串p。

问题可转化为：将01序列p构建AC自动机，找出一个Trie图上的环，使得其不经过危险节点。
将01序列构成trie图，然后搜索不经过危险节点的路径，如果搜索到了之前搜索过的节点就说明存在一个环。
ps：第一次写trie图

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
char s[31000];
struct trie
{
    trie *c[2],*fail;
    bool dang,vis;
    trie(){c[0]=c[1]=fail=NULL; vis=dang=0;}
}*root=new trie();

void insert(char *st)
{
    int len=strlen(st);
    trie *p=root;
    for(int i=0;i!=len;++i)
    {
        if(!p->c[st[i]-'0']) p->c[st[i]-'0']=new trie();
        p=p->c[st[i]-'0'];
    }
    p->dang=1;
}
void build()
{
    static trie *q[30100];
    int l=1,r=0;
    if(root->c[0]) root->c[0]->fail=root,q[++r]=root->c[0];
    else root->c[0]=root;
    if(root->c[1]) root->c[1]->fail=root,q[++r]=root->c[1];
    else root->c[1]=root;
    trie *p;
    while(l<=r)
    {
        p=q[l++];
        if(p->c[0]) p->c[0]->fail=p->fail->c[0],q[++r]=p->c[0],p->c[0]->dang|=p->fail->c[0]->dang;
        else p->c[0]=p->fail->c[0];
        if(p->c[1]) p->c[1]->fail=p->fail->c[1],q[++r]=p->c[1],p->c[1]->dang|=p->fail->c[1]->dang;
        else p->c[1]=p->fail->c[1];
    }
}
bool dfs(trie *x)
{
    if(x->dang) return false;
    if(x->vis) return true;
    x->vis=1;
    if(dfs(x->c[0])) return true;
    if(dfs(x->c[1])) return true;
    x->dang=1; return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s);
        insert(s);
    }
    build();
    if(dfs(root)) puts("TAK");
    else puts("NIE");
    return 0;
}