题目核心是多模式匹配，所以考虑用对所有模式串建立AC自动机。
我们把自动机上，存在一个模式串作为前缀的节点，称作“危险节点”。
如果无限长的安全代码存在的话，匹配过程中Trie图上一定有节点会经过多次，即存在环；而且经过的所有节点都不是“危险节点”，否则就包含病毒代码段了。
所以我们只需要看Trie图上是否存在不包含危险节点的环，就能得到答案了。
可以用一个dfs实现这一过程。用\(vis\)来表示节点访问状态，初始全为\(0\)：
- \(vis[u]=0\)：\(u\)未被访问过。
- \(vis[u]=1\)：\(u\)正在处理中。
- \(vis[u]=-1\)：从\(u\)出发找不到环。
如果只用\(0,1\)而不用\(-1\)来剪枝优化，时间复杂度可能由线性退化到指数级，将无法通过hack数据。
bool dfs(int u){
if(vis[u]==1) return 1;
if(vis[u]==-1) return 0;
vis[u]=1;
for(int i=0;i<C;i++)//C=2
if(!en[tr[u][i]]&&dfs(tr[u][i]))
return 1;//en[x]=1表示x是危险节点
vis[u]=-1;
return 0;
}
最后就是如何判断某个节点是不是危险节点，这个可以在get_fail()中处理出来。如果节点\(u\)是模式串的结尾，或者\(fail[u]\)是危险节点，那么\(u\)就是危险节点。
时间复杂度\(O(\sum|s|\times |\Sigma|)\)。
点击查看代码
#include<bits/stdc++.h>
#define N 30010//节点数（模式串总长）
#define C 2//字符集大小
using namespace std;
int n,tr[N][C],fail[N],cnt;
int q[N],head,tail,vis[N];
bool en[N];
string s;
void ins(string s){
int p=0;
for(char i:s){
int c=i-'0';
if(!tr[p][c]) tr[p][c]=++cnt;
p=tr[p][c];
}
en[p]=1;
}
void get_fail(){
head=0,tail=-1;
for(int i=0;i<C;i++) if(tr[0][i]) q[++tail]=tr[0][i];
while(head<=tail){
int u=q[head++];
for(int i=0;i<C;i++){
int& v=tr[u][i];
if(v) fail[v]=tr[fail[u]][i],q[++tail]=v,
en[v]|=en[fail[v]];
else v=tr[fail[u]][i];
}
}
}
bool dfs(int u){
if(vis[u]==1) return 1;
if(vis[u]==-1) return 0;
vis[u]=1;
for(int i=0;i<C;i++)
if(!en[tr[u][i]]&&dfs(tr[u][i]))
return 1;
vis[u]=-1;
return 0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
ins(s);
}
get_fail();
if(dfs(0)) cout<<"TAK\n";
else cout<<"NIE\n";
return 0;
}