二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
对于多串，先建立AC自动机。
然后考虑对于没有病毒代码的代码来说，它会在AC自动机上一直走直到跳出。
而如果走出了一个环的话就意味着它可以沿着这个环无限延伸——这就是我们所要求的。
所以我们建立AC自动机跑dfs搜环（当然危险节点不能走），如果有环就是TAK，否则就是NIE。
#include #include #include #include #include #include #include using namespace std;const int N=2010;const int M=30010;struct trie{ bool ed; int a[2],fail;}tr[M*20];int cnt=0;char s[M];inline void insert(){ int now=0; int len=strlen(s); for(int i=0;i
q; tr[0].fail=0; for(int i=0;i<2;i++){ if(tr[0].a[i]){ tr[tr[0].a[i]].fail=0; q.push(tr[0].a[i]); } } while(!q.empty()){ int u=q.front(); q.pop(); for(int i=0;i<2;i++){ if(tr[u].a[i]){ int v=tr[u].a[i]; tr[v].fail=tr[tr[u].fail].a[i]; tr[v].ed|=tr[tr[v].fail].ed; q.push(tr[u].a[i]); }else{ tr[u].a[i]=tr[tr[u].fail].a[i]; } } } return;}bool vis[M*20],met[M*20];bool dfs(int u){ vis[u]=1; for(int i=0;i<2;i++){ int v=tr[u].a[i]; if(vis[v])return 1; if(tr[v].ed||met[v])continue; met[v]=1; if(dfs(v))return 1; } vis[u]=0; return 0;}int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>s; insert(); } getfail(); if(dfs(0))puts("TAK"); else puts("NIE"); return 0;}