题目大意：给定n个01串，问是否存在一个无限长的01串，不包含这n个01串中的任何一个
建出Trie图之后判环即可
我这傻逼一开始居然跑了一个DFS去判环23333
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 30300using namespace std;int n;char s[M];namespace Aho_Corasick_Automaton{struct Trie{Trie *son[2],*fail;bool ed;short into;}*root,mempool[M],*C=mempool;void Insert(Trie *&p,char *pos){if(!p) p=new (C++)Trie;if(!*pos){p->ed=true;return ;}Insert(p->son[*pos-'0'],pos+1);}void Build_Tree(){static Trie *q[M];int i,r=0,h=0;for(i=0;i<2;i++)if(root->son[i])(q[++r]=root->son[i])->fail=root;elseroot->son[i]=root;while(r!=h){Trie *p=q[++h];for(i=0;i<2;i++){if(p->son[i]){p->son[i]->fail=p->fail->son[i];p->son[i]->ed|=p->son[i]->fail->ed;q[++r]=p->son[i];}elsep->son[i]=p->fail->son[i];}}}bool Find_Ring(){static Trie *temp,*q[M];int i,r=0,h=0,cnt=0;for(temp=mempool;temp<C;temp++)if(!temp->ed){++cnt;for(i=0;i<2;i++)temp->son[i]->into++;}for(temp=mempool;temp<C;temp++)if(!temp->into&&!temp->ed)q[++r]=temp;while(r!=h){Trie *p=q[++h];for(i=0;i<2;i++)if(!–p->son[i]->into&&!p->son[i]->ed)q[++r]=p->son[i];}return cnt!=r;}}int main(){using namespace Aho_Corasick_Automaton;int i;cin>>n;for(i=1;i<=n;i++){scanf("%s",s+1);Insert(root,s+1);}Build_Tree();puts(Find_Ring()?"TAK":"NIE");return 0;}
，而只有在充满了艰辛的人生旅途中，始终调整好自己观风景的心态，
