D. 病毒

题目描述

原题来自：POI 2000

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：例如如果 {011,11,00000}\{011, 11, 00000\}{

011,11,00000} 为病毒代码段，那么一个可能的无限长安全代码就是 010101⋯010101\cdots 010101⋯。如果 {01,11,000000}\{01, 11, 000000\}{

01,11,000000} 为病毒代码段，那么就不存在一个无限长的安全代码。

请写一个程序，读入病毒代码，判断是否存在一个无限长的安全代码，将结果输出。

输入格式

第一行包括一个整数 nnn，表示病毒代码段的数目；

以下的 nnn 行，每一行都包括一个非空的 010101 字符串——就是一个病毒代码段。

输出格式

第一行输出一个单词。假如存在这样的代码，则输出 TAK，否则输出 NIE。

样例

样例输入

301 11 00000

样例输出

NIE

数据范围与提示

对于全部数据，所有病毒代码段的总长度不超过 3×10⁴4​​。

 

对trie图的理解还是没有那么透彻啊(以前就只是知道他比trie树快…)。

安全的串可以在AC自动机上在不匹配单词终点的情况下无限匹配（颓题解之前就想到这里）， 在trie图上，如果能无线匹配那么意味着trie图上有环，dfs判环即可。

注意还有两个剪枝（zz的我刚开始居然用队列模拟深搜…）：

1.单词终点不能走，那么fail指向单词终点的点也不能走。设一个单词终点为x，y->fail=x，那么root~x为root~y的后缀，y也不能走。将x设为危险节点，fail指向x的y也是危险节点，同理所有fail指向危险节点的点都是危险节点（之前一直不能理解这玩意儿有啥用），dfs时将危险节点剪掉。

2.由于一个节点可能会搜多次，所以将搜索过但是return 0的节点标记，剪掉。

#include
      
       #include
       
        using namespace std;struct trie{    int count;    bool pd,danger,vis;    trie *next[2],*fail;    trie()    {        count=0;pd=0;danger=0;vis=0;        next[1]=next[2]=fail=NULL;    }}*q[100000],*root=new trie();int head,tail;void insert(char s[],trie *root){    trie *p=root;    int i=0,index;    while(s[i])    {        index=s[i]-'0';        if(p->next[index]==NULL)p->next[index]=new trie();        p=p->next[index];        i++;    }    p->count++;    p->danger=1;}void build_ac(trie *root){    q[++tail]=root;    while(head!=tail)    {        trie *p=q[++head];        trie *temp=NULL;        for(int i=0;i<=1;i++)        if(p->next[i])        {            if(p==root)      p->next[i]->fail=p;            else                        {                p->next[i]->fail=p->fail->next[i];                if(p->fail->next[i]->danger)p->next[i]->danger=1;            }                q[++tail]=p->next[i];        }        else            if(p==root)       p->next[i]=root;            else           p->next[i]=p->fail->next[i];    }}bool dfs(trie *p){    p->pd=1;    for(int i=0;i<=1;i++)    {        if(p->next[i]->pd)return 1;        if(p->next[i]->danger || p->next[i]->vis)continue;        if(dfs(p->next[i]))return 1;        p->next[i]->vis=1;    }        p->pd=0;    return 0;}int n;char keyword[30010];char str[100000];signed main(){    //freopen("in.txt","r",stdin);    cin>>n;    for(int i=1;i<=n;i++)    {        scanf("%s",keyword);        insert(keyword,root);    }    build_ac(root);    if(dfs(root))cout<<"TAK";    else           cout<<"NIE";}