学习心得 - 字符串 - ACAM
ExFish
·
·
算法·理论
前言
所谓 AC 自动机就是 KMP+Trie，不算很难。
问题
我们发现，$n=1$ 时这玩意就是个 KMP。
然后，我们可以对模式串建 Trie。
### 例子
例如，$s=[\tt i, he, his, she, hers]$。
我们简单建一下普通的 Trie。
这时，我们有文本串 $\tt shersheishis$。
我们发现，第 $1$ 次匹配成功 $\tt she$，但是下一个 $\tt r$ 失配了，我们这时要从头来么？
显然不优，可以试图采用 KMP 的思想，类似 $next$ 指针，跳跃。
这时我们就要引入 $fail$ 指针了。
### $fail$ 指针
含义：在点 $i$ 失配后，调到 $fail_i$ 指向的 $j$，**实现 KMP 的跳跃功能**。
我们首先画出 $fail$ 指针，才能更好理解。
首先，我们将 $root$ 的 $fail_i$ 和其的子节点的 $fail_i$ 设为 $root(0)$。
然后，我们要求一个点的 $fail_i$，设其为 $p$，先要走到这个点的父亲。
然后直接跳 $fail_{fa_i}$。
要是有一个子节点 $q$，字符 $=ch_p$，那么 $fail_p=q$。
要是一直失配，那么连到 $root(0)$。
即，后退，跳跃，标记。
我们发现，这是一个递归的过程。
实现中我们常用 BFS 完成 `getf()`。
这样就可以非常好理解的完成求解 $fail$ 指针，效果与 $next$ 几乎一样。
#### 代码
咕咕咕。
### 查询
参造 Trie 的查询方法，搞一个 $p$ 来跳，要是失配就跳 fail，应该就可以了。
#### 代码
咕咕咕。
### 拓扑排序优化
如题，[超时了](https://www.luogu.com.cn/record/199471420)。
怎么办？
我们先用上图的例子。
我们把 $fail$ 边拿出来。
如下。
显然，因为每个点都有 $fail$ 边，然后 $root$ 的边没了，所以就形成了一个 $n-1$ 条边的连通图，就是**树**。
考虑在树上拓扑排序，用入度小的边更新入度大的边，就能不跳 $fail$ 边统一更新答案。
---
参考资料：[图解 AC 自动机](https://www.bilibili.com/video/BV18q4y1Q7Mr/?spm_id_from=333.1391.0.0&vd_source=9a0903c5089f7500f1328de5270464d0)，[AC 自动机](https://www.luogu.com/article/7vp0dxaw)，[题解：AC 自动机](https://www.luogu.com.cn/article/w9kufs8z)。