思路：
要求构建一个字符串，使得这个字符串不包含给出的任意一个单词。
如果我们已经构建出了一个安全代码，放在ac自动机上跑，那么我们必定不能得到任何一个字符串，此时我们得到的fail指针必定是在一个环上循环，并且这个环不包含单词的末尾。
我们也知道fail指针最后是会指回0点的，那么此时我们其实就是要求一个环，这个换不包含单词末尾即可。加一个优化就是，如果fail指针指向的地方是末尾，那么这个地方等同于末尾。
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1000010; char s[maxn],p[maxn]; int trie[maxn][26],cntword[maxn],fail[maxn],cnt=0; int n; bool vis[maxn],ins[maxn]; void insert(char *s){ int root=0; int si=strlen(s); for(int i=0;i<si;i++) { int Next=s[i]-‘0‘; if(!trie[root][Next])trie[root][Next]=++cnt; root=trie[root][Next]; } cntword[root]++; } void getfail(){ queue<int >q; for(int i=0;i<=1;i++) { if(trie[0][i]){ q.push(trie[0][i]); } } while(!q.empty()) { int now=q.front(); q.pop(); for(int i=0;i<=1;i++) { if(trie[now][i]){ fail[trie[now][i]]=trie[fail[now]][i]; if(cntword[fail[trie[now][i]]])cntword[trie[now][i]]=1;//如果fail指针指向的是病毒的末尾，那么这个也是病毒 q.push(trie[now][i]); }else{ trie[now][i]=trie[fail[now]][i]; } } } } void init(){ clr(trie,0); clr(cntword,0); clr(ins,0),clr(vis,0); } bool dfs(int u) { ins[u]=1; for(int i=0;i<=1;i++) { int v=trie[u][i]; if(ins[v]==1)return true; if(vis[v]||cntword[v])continue; vis[v]=1; if(dfs(v))return true; } ins[u]=0; return false; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",p); insert(p); } fail[0]=0; getfail(); if(dfs(0))puts("TAK"); else puts("NIE"); }
原文：https://www.cnblogs.com/mountaink/p/10506851.html
