|
|
## [$P2444$ [$POI2000$]病毒](https://www.luogu.com.cn/problem/P2444)
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，**是否存在一个无限长的安全的二进制代码**。
|
|
|
|
|
|
**示例**：
|
|
|
|
|
|
* 如果 $\{011, 11, 00000\}$ 为病毒代码段，那么一个可能的无限长安全代码就是 $010101 \ldots010101$…
|
|
|
|
|
|
* 如果 $\{01, 11, 000000\}$ 为病毒代码段，那么就不存在一个无限长的安全代码
|
|
|
|
|
|
现在给出所有的病毒代码段，判断是否存在无限长的安全代码。
|
|
|
|
|
|
|
|
|
### 二、解题思路
|
|
|
|
|
|
#### $Q$:如何确定它是安全的？
|
|
|
|
|
|
有了$fail$指针，$trie$树就不是原来的树型结构了，我们可以把它叫做$trie$图，由父节点向子节点连的边和$fail$代表的边构成（都是单向边）。
|
|
|
|
|
|
最模板的$AC$自动机，就是直接匹配字符串。然而这题思维并非如此简单。
|
|
|
|
|
|
来一波逆向思维。假设我们**构造出了一个无限长的** <font color='red'><b>安全代码</b></font> ，再拿到$AC$自动机上匹配，会发生什么？
|
|
|
|
|
|
没错，当我们一位一位地匹配的时候，我们会发现，**永远都不会跳到某个病毒代码段结尾的位置**（以后把这里称作 <font color='red'><b>危险节点</b></font> ，因为匹配到此处表明已经出现了某个病毒代码段），然后似乎会在**自动机里永无止境地打转转**。。。。。。
|
|
|
|
|
|
既然这个自动机又像一个图，那我们的问题不就变成了——在$AC$自动机($trie$图)中寻找一个环，并且 <font color='red'><b>环上没有任何危险节点</b></font> ，并且还要注意，**这个环能被根节点访问到**（也就是说从根节点出发能在不经过危险节点的情况下走到到这个环，不然在模拟$AC$自动机匹配的时候无法到达这个这个环，也就失去了意义）。
|
|
|
|
|
|
找环就属于图论了，$dfs$一遍，**只不过必须从根节点出发**。
|
|
|
|
|
|
开两个布尔数组:
|
|
|
|
|
|
* 一个记录历史是否访问过
|
|
|
* 一个记录是否在搜索的栈中
|
|
|
|
|
|
如果搜索过程中发现将要访问的下一个节点之前已经入栈了，就找到解了
|
|
|
|
|
|
不走危险节点，不走历史访问过而已经不在栈中的节点。
|
|
|
|
|
|
还注意一下，如果某节点$fail$指向的是危险节点，那么该节点也是危险节点，$AC$自动机的性质，这里不再赘述。
|
|
|
|
|
|
### 三、实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#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;
|
|
|
}
|
|
|
```
|
