Aho–Corasick 算法（常简称 AC 自动机）由 Alfred V. Aho 与 Margaret J. Corasick 于 1975 年提出， 用于在一段文本中同时查找多个模式串（关键词、敏感词、病毒特征码、路由前缀等）。 它把多个模式串合并成一棵字典树（Trie），再为每个节点补上失败指针（failure link）， 扫描文本时遇到不匹配可沿失败链回退，而无需从头重试，因此整体复杂度与文本长度线性相关。
Trie 存模式 + 失败链像 KMP + 一次扫完全文 → 多模式匹配 O(n)。
把所有模式串插入字典树，共享公共前缀，节省空间。
BFS 为每个节点找「最长真后缀且为 Trie 中前缀」的节点，类似 KMP 的 next。
按字符在 Trie 上走；走不动就沿 fail 回退；经过带输出的节点即报告匹配。
典型应用：敏感词过滤、入侵检测（Snort 等）、DNA 序列 motif 搜索、IDE 多关键字高亮、路由表最长前缀匹配、日志多关键词检索。
| 方法 | 预处理 | 查询（文本长 n，模式总长 m，模式数 k） | 特点 |
|---|---|---|---|
| 暴力多模式 | 无 | O(n · m) 或 O(n · k·平均长) | 实现简单，模式多或文本长时慢 |
| KMP（单模式） | O(模式长) | O(n) 每个模式扫一遍 → O(k·n) | 单模式最优之一，多模式需重复扫描 |
| Rabin–Karp | O(模式长) | 期望 O(n+m)，最坏 O(n·m) | 滚动哈希，适合随机文本；需处理哈希冲突 |
| Aho–Corasick | O(m) 建 Trie + fail | O(n + 匹配次数) | 多模式一次扫描；匹配很多时输出本身也占时间 |
记法：n = 文本长度，m = 所有模式字符总数，k = 模式个数。
Trie + fail + 输出链表（output）。适合离线建表、内存中多模式匹配。
优点：理论清晰、一次扫描、共享前缀。缺点：模式极多或字符集大时 Trie 占内存；动态增删模式需重建或复杂维护。
用双数组 Trie（DAT）存转移，节点密集、缓存友好。常见于 ahocorasick（C++/Python）、部分分词与防火墙引擎。
优点：省内存、扫描快。缺点：构建复杂，动态更新困难。
Intel Hyperscan、部分 SIMD 实现用位图并行处理多字节，适合固定规则库、高吞吐网络检测。
优点：极高吞吐。缺点：规则编译耗时、平台依赖、不适合随意改规则的教学场景。
先用 Bloom 粗判「文本是否可能含某类模式」，再对候选片段跑 AC，减少全量扫描（大规模规则库常见）。
优点：降低平均成本。缺点：多一层假阳性设计；架构更复杂。
理论更强，可处理更多后缀结构问题；实现与常数因子通常比 AC 重，工程上多模式「子串出现」仍首选 AC。
| 变体 / 方案 | 适用场景 | 主要优点 | 主要缺点 |
|---|---|---|---|
| 标准 AC | 教学、中等规模词库、应用内过滤 | 实现直接、O(n) 扫描 | 大字母表 / 超大规模模式占内存 |
| DAT / 压缩 Trie | 生产词库、分词 | 紧凑、快 | 构建难、不易热更新 |
| Hyperscan / SIMD | 网关 IDS、DPI | 吞吐极高 | 编译期、硬件与授权限制 |
| AC + Bloom 两级 | 百万级规则、稀疏命中 | 均摊成本低 | 系统设计复杂 |
| 多次 KMP / 正则引擎 | 模式极少或需复杂语法 | 灵活（正则） | 多模式时不如 AC 省扫描次数 |
aaa 中模式 aa 出现 2 次）a，模式 a）