BZOJ 2938 Poi2000 病毒 AC自动机+拓扑排序
题目大意:给定n个01串,问是否存在一个无限长的01串,不包含这n个01串中的任何一个
建出Trie图之后判环即可
我这傻逼一开始居然跑了一个DFS去判环23333
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 30300 using 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; else root->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]; } else p->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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。