Aho–CorasickAho–Corasick
把多个模式构成 Trie，并用失败链接复用已匹配后缀。
- 核心约束
- 失败链接指向可继续匹配的最长有效后缀状态。
- 适用问题
- 多模式文本匹配，z 为报告的匹配数量。
- 边界与取舍
- 输出数量可能很大；字母表与转移表示影响内存。
时间与空间#
S 为全部模式的总长度，n 为文本长度，z 为报告的匹配数，R 为字母表大小。
- 时间复杂度
- 扫描 ；构建取决于转移表示
- 辅助空间
- 稀疏自动机约 ；完整转移表
固定字母表、常数时间转移时成立；报告所有重叠匹配必须计入 z。输出链接避免在每节点复制全部后缀匹配集合。构建完整 DFA 需填充转移表，不能无条件写成 。
基础原理参考资料
Aho & Corasick 1975 · Efficient string matching多模式匹配自动机和失败转移的原始论文。
aho-corasick 1.1.3 · Automata自动机表示、匹配语义和空间速度权衡。