5.5 KiB
P2444 [POI2000]病毒
一、题目描述
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
-
如果
\{011, 11, 00000\}为病毒代码段，那么一个可能的无限长安全代码就是010101 \ldots010101… -
如果
\{01, 11, 000000\}为病毒代码段，那么就不存在一个无限长的安全代码
现在给出所有的病毒代码段，判断是否存在无限长的安全代码。
二、解题思路
Q:如何确定它是安全的？
有了fail指针，trie树就不是原来的树型结构了，我们可以把它叫做trie图，由父节点向子节点连的边和fail代表的边构成（都是单向边）。
最模板的AC自动机，就是直接匹配字符串。然而这题思维并非如此简单。
来一波逆向思维。假设我们构造出了一个无限长的 安全代码 ，再拿到AC自动机上匹配，会发生什么？
没错，当我们一位一位地匹配的时候，我们会发现，永远都不会跳到某个病毒代码段结尾的位置（以后把这里称作 危险节点 ，因为匹配到此处表明已经出现了某个病毒代码段），然后似乎会在自动机里永无止境地打转转。。。。。。
既然这个自动机又像一个图，那我们的问题不就变成了——在AC自动机(trie图)中寻找一个环，并且 环上没有任何危险节点 ，并且还要注意，这个环能被根节点访问到（也就是说从根节点出发能在不经过危险节点的情况下走到到这个环，不然在模拟AC自动机匹配的时候无法到达这个这个环，也就失去了意义）。
找环就属于图论了，dfs一遍，只不过必须从根节点出发。
开两个布尔数组:
- 一个记录历史是否访问过
- 一个记录是否在搜索的栈中
如果搜索过程中发现将要访问的下一个节点之前已经入栈了，就找到解了
不走危险节点，不走历史访问过而已经不在栈中的节点。
还注意一下，如果某节点fail指向的是危险节点，那么该节点也是危险节点，AC自动机的性质，这里不再赘述。
三、实现代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n; //模式串数量
char s[N]; //模式串
// Trie树
int tr[N][2], idx;
int cnt[N];
void insert(char *s) {
int p = 0;
for (int i = 0; s[i]; i++) {
int t = s[i] - '0';
if (!tr[p][t]) tr[p][t] = ++idx;
p = tr[p][t];
}
cnt[p]++; //记录以p点为结尾的模式串数量+1，也就是说它是危险节点
}
// AC自动机
int q[N], ne[N];
void bfs() {
int hh = 0, tt = -1;
for (int i = 0; i < 2; i++) //将第一层存在的节点入队列
if (tr[0][i]) q[++tt] = tr[0][i];
while (hh <= tt) {
int p = q[hh++];
for (int i = 0; i < 2; i++) {
int t = tr[p][i];
if (!t)
tr[p][i] = tr[ne[p]][i];
else {
ne[t] = tr[ne[p]][i];
q[++tt] = t;
// tr[t][i]这个节点，它的失配指针指向的节点，也是危险节点的话，那么，当前节点也是危险节点
if (cnt[ne[t]]) cnt[t]++;
}
}
}
}
// dfs在trie树上判环的代码模板
int st[N];
bool dfs(int u) { //在AC自动机上判环
if (st[u] == 1) return true; //如果在判环过程中发现重复访问的点，说明存在环
if (st[u] == -1) return false; //如果以前检查过这个点u,结果一条路跑过黑，都没有检查出来过有环，那么下次如果再让我检查点u,就直接返回结果就可以了
st[u] = 1; //当前路径上走过了点u
for (int i = 0; i <= 1; i++) { //二进制，必然每个节点有两条分叉边，0和1
if (!cnt[tr[u][i]]) { //如果tr[u][i]这个点是危险点的话,就避让开；如果不是危险点的话，就继续探索它
if (dfs(tr[u][i])) return true; // 如果后续发现存在环，那么我也可以上报信息：我的后代子孙中发现环，也就是我这一脉中存在环;
//如果tr[u][i]及后续不存在环，那还需要继续检查，不能直接返回 dfs(tr[u][i]),这一块要注意写法，也算是一种代码模板，需要背诵下来
}
}
st[u] = -1; //一条道跑到黑，都没有找出后续节点中存在环，那么标识上，防止以后重复查询本节点
return false; //如果找到了环，中途就会返回true,都跑到这里了，表示没有找到环
}
int main() {
//加快读入
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s;
insert(s);
}
//构建AC自动机
bfs();
//从root出发，开始判断是不是存在环
dfs(0) ? puts("TAK") : puts("NIE");
return 0;
}