题解 P2444 【[POI2000]病毒】

## 思路概述 我们知道，AC自动机是一种多模字符串匹配算法。构造 Trie 树 后，在模式串末尾一位的结点作上标记。平常的 AC自动机 是尽量能多接触到这些标记，使总值最大。本题倒是有点奇葩，要构造一个可行的无限长文本串，使没有任何子串为给出模式串中的一个。也就是说，我们需要让平常 AC自动机 的查询操作，尽量避免标记，能用失配指针跳转就跳转。 因为要有无限长的可行串，根据 AC自动机 的原理，我们可以将结点连接到儿子的边当作一条单向边，同时失配指针也当作一条单向边，如果存在一个环，且环上没有任何危险标记（即病毒代码段末尾一位的结点专门作的编号），此时 AC自动机 能一直在环上匹配，并且永远也不会得到为模式串的一个子串，就像程序中的死循环一样。这个找环我们可以通过 dfs 来实现。 ## 注意事项 - 1 . 我们需要建立两个布尔数组，其中一个布尔数组记录每个节点在当前 dfs 走的路径上有没有被选中，另一个布尔数组记录每个节点历史上有没有被访问过。如果当前路径形成回路，就找到环了，应该还是比较好实现的。 - 2 . 避免危险标记，也就是说如果下一个结点拥有危险标记，就不走那个结点。 - 3 . 在构造失配指针时，一个很明显的优化是：如果一个结点拥有了失配指针，它指向的结点如果有危险标记，自己必然也危险，因为它到根结点形成的串是自己到根节点的后缀。 ## 代码实现 代码和注释都认认真真打了，如果上面的概述有点难懂的话……请结合代码和该行的注释进行理解吧。 ```cpp #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> using namespace std; queue < int > Q; // 标失配结点编号所需的队列 struct Node{ int t[2] , f; // t 数组为下个二进制位结点编号，f 为失配结点编号 bool c; // c 变量为该结点是否为危险代码段的最后一位 }; // 定义字典树结点结构体 struct AcAutomaton{ Node N[30001]; // 字典树的结点 int S = 0; // 字典树的当前非根节点总数 inline void Insert(char c[] , int l){ int nd = 0; // 定义当前点，当然从根节点 0 开始 for(int i = 0 ; i < l ; i++) if(N[nd].t[c[i] - 48] == 0) N[nd].t[c[i] - 48] = ++S , nd = S; // 没有目标节点，新建个 else nd = N[nd].t[c[i] - 48]; // 有目标节点，直接转移当前点 N[nd].c = true; // 标上病毒段末尾的危险标记 } // 函数：向字典树内插入长度为 l 的病毒串 inline void PutFail(){ if(N[0].t[0] > 0) Q.push(N[0].t[0]); // 根节点有没有 0 儿子，如果有推入队列 if(N[0].t[1] > 0) Q.push(N[0].t[1]); // 根节点有没有 1 儿子，如果有推入队列 while(!Q.empty()){ int nd = Q.front() ; Q.pop(); // 得到队列首 for(int i = 0 ; i <= 1 ; i++) if(N[nd].t[i] > 0){ Q.push(N[nd].t[i]); int td = N[nd].f; while(td > 0 && N[td].t[i] <= 0) td = N[td].f; // 要不到根节点，要不找到最长匹配后缀段 if(N[td].t[i] <= 0) N[N[nd].t[i]].f = 0; // 失配指针转移到根节点 else{ N[N[nd].t[i]].f = N[td].t[i]; if(N[N[td].t[i]].c) N[N[nd].t[i]].c = true; // 既然自己后缀都行不通，自己也危险 } }else N[nd].t[i] = N[N[nd].f].t[i]; } } // 函数：设置失配指针 }; // 定义 AC 自动机结构体 AcAutomaton A; // 新建 AC 自动机 bool v[30001]; // v 为结点是否是当前搜索路径上的一点 bool f[30001]; // f 为结点是否是否被现在或过往搜索过 char c[30001]; int n; void Dfs(int d){ // 通过搜索寻找有没有环 v[d] = true; // 作下路径标记 for(int i = 0 ; i <= 1 ; i++) if(v[A.N[d].t[i]]){ // 根据路径标记判断是否拥有环 printf("TAK"); exit(0); // 找到了环，输出并退出程序 }else if(!A.N[A.N[d].t[i]].c && !f[A.N[d].t[i]]){ // 只有下一位不为危险结点并且有可能成环，才递归搜索 f[A.N[d].t[i]] = true; // 下一个结点已经被搜索过了 Dfs(A.N[d].t[i]); } v[d] = false; // 抹除路径标记 } int main(){ scanf("%d" , &n); // 输入病毒串数量（这个不用我打注释了吧……） for(int i = 1 ; i <= n ; i++) scanf("%s" , c) , A.Insert(c , strlen(c)); // 输入并插入病毒串; A.PutFail(); // 设置每个结点的失配指针 Dfs(0); // 从字典树的根结点开始找环 printf("NIE"); // 既然程序没有退出，就输出无解 return 0; } ```