118-字符串-AC自动机

核心概述

AC 自动机用于多模式匹配，将若干模式构建为带失败指针的自动机，以线性时间在文本中检索全部出现位置，契合仓库中字符串类模板的接口与语义约定。

原文引述

KACTL algorithms should be: useful, short, fast enough, well tested, and if relevant, readable and easy to modify. They should not be overly generic, since code is manually typed and that just adds overhead. ——摘自 kactl/README.md

展开阐述

• 定义与背景

  • 目标：给定若干模式串，在线性扫描文本时同时识别所有模式出现。
  • 结构：基于 Trie（字典树）并为每个结点维护失败指针（类似 KMP 的失配转移），从而在失配时常数时间跳转到最长可匹配后缀状态。

• 接口与输入输出语义（按仓库约定）

  • 典型接口（据约定风格）：
    • add(pattern)：插入一个模式串。
    • build()：构建失败指针与自动机转移。
    • query(text) → 报告匹配（位置、模式索引计数等按实现约定）。
  • 语义：
    • 多次 add 后一次 build；query 返回总匹配数或逐位匹配详情（依实现约定统一返回结构）。

• 核心流程与关键要点

  • 构建：
    • 先建 Trie；根的直接儿子的失败指向根；其余用 BFS 计算 fail[u] = go(fail[parent[u]], ch)。
    • 继承计数：可将 fail 链上的出现次数累加至当前结点（按实现需要）。
  • 查询：
    • 状态转移：cur = go(cur, ch)；在每步访问结点及其 fail 链上累加匹配。
  • 字符集：
    • 若为小写字母，可定长数组；若为一般字符，使用映射结构（参见 005-数据结构-哈希表 的工程取舍）。

• 复杂度与边界条件

  • 构建：O(总模式长度)。
  • 查询：O(文本长度 + 匹配数)。
  • 边界：空模式（通常忽略）、重复插入的模式（可计数）、大字符集需注意空间与常数。

• 与相邻技术的取舍对比

  • 单模式请参见 KMP（蓝图中相邻条目）；多模式与哈希类方法相比，AC 在最坏情况下仍具线性上界，避免哈希碰撞不确定性。
  • 模式全为等长或需要滚动窗口指纹时，可参考 119-字符串-字符串哈希 的场景取舍。

关联节点

• 005-数据结构-哈希表