题目描述
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
输入格式：
在文本文件WIR.IN的第一行包括一个整数n(n≤2000)，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
输出格式：
在文本文件WIR.OUT的第一行输出一个单词：
TAK——假如存在这样的代码；
NIE——如果不存在。
题解：
总长度不超过30000启发我们用trie，多个模式串匹配，启发我们用AC自动机。
但是，一般的问题是，构造一个给定长度的串，使得出现若干个模式串等问题。
通常用dp解决。
但是这个题就比较新奇了。
问你能不能构造一个无限长的串，不存在一个模式串。
怎么处理无限问题？
那么一定要考虑，为什么是无限的？
也许有个循环节？可以考虑
也可以反过来，考虑，如果我们把这个无限长的串，放在AC自动机上匹配，
那么，最终的结果是，一定存在一个无限长的串，通过跳fail，可以在AC自动机上不断循环在一个环上。
证明：
我们把儿子指针作为一个向下的有向边，fail指针作为一个返祖边或者横叉边
记AC自动机上的点代表的子串包含一个病毒代码的点称为危险点。
对于AC自动机有环的情况，一定可以构造一个无限长的串。（先匹配到这个点，然后环上循环即可。）
对于没有环的情况，匹配时一个节点一定只会经过一次。否则就有环了。
那么，匹配下去，由于串无限长，节点有限个，那么必然会经过一个危险点，无解。
证毕。
所以， AC自动机建好后，类似Tarjan判环(强连通分量)即可。
代码：
#includeusing namespace std;typedef long long ll;const int N=2002;const int M=30000+5;struct AC{ int ch[M][2],cnt; int fail[M]; bool has[M]; void ins(char *s){ int len=strlen(s+1); int now=0; for(int i=1;i<=len;i++){ int x=s[i]-'0'; if(!ch[now][x]) ch[now][x]=++cnt; now=ch[now][x]; } has[now]=1; } void build(){ queue q; for(int i=0;i<=1;i++) if(ch[0][i]) fail[ch[0][i]]=0,q.push(ch[0][i]); while(!q.empty()){ int x=q.front();q.pop(); has[x]|=has[fail[x]]; for(int i=0;i<=1;i++){ if(ch[x][i]){ fail[ch[x][i]]=ch[fail[x]][i]; q.push(ch[x][i]); } else ch[x][i]=ch[fail[x]][i]; } } }}t;int n;char s[M];int dfn[M],low[M],df;int sta[M],top;bool in[M];bool fl;void dfs(int x){ if(fl) return; dfn[x]=low[x]=++df; sta[++top]=x; in[x]=1; for(int i=0;i<=1;i++){ if(t.has[t.ch[x][i]]) continue; if(!dfn[t.ch[x][i]]){ dfs(t.ch[x][i]); low[x]=min(low[x],low[t.ch[x][i]]); } else if(in[t.ch[x][i]]) low[x]=min(low[x],dfn[t.ch[x][i]]); } if(low[x]==dfn[x]){ int sz=0; int z; do{ z=sta[top--]; sz++; in[z]=0; }while(z!=x); if(sz>1) fl=true; }}int main(){ scanf("%d",&n); fl=false; for(int i=1;i<=n;i++){ scanf("%s",s+1); t.ins(s); } t.build(); dfs(0); puts(fl?"TAK":"NIE"); return 0;}
总结：
怎么说，POI的题目就是脑洞新奇~~
思考的关键点在于，为什么可以构造出无限长的，把这个串往AC自动机上匹配会怎么样？
其实是比较自然的想法。毕竟怎么问，怎么考虑。
