AC自动机

AC自动机主要用于多模式串的匹配
AC自动机是基于字典树 Tier 的，在匹配失败时，并不完全回退，而是到达 fail 指针那里

fail 指针的构造方式为：

  • 通过 BFS 的方式来构造
  • 第一层节点的 fail 指向根节点
  • 对于任何一个节点，其 fail 为： paren->fail->fail-> ... ->child(current)；如果不存在，那么其 fail 指向根节点。（这里用了递归的思想）

fail 的时候发生了什么：（当前已经匹配的模式串会变化）
image.png

如图：
image.png
AC自动机的代码为：
TODO：应该再明确 AC 自动机是干什么的，以及该怎么用。