Aho–Corasick 自动机

单模式匹配中，KMP 算法公理库KMP 算法Knuth–Morris–Pratt algorithm利用模式自身前后缀信息避免文本指针回退的线性时间字符串匹配算法。用前缀函数公理库前缀函数Prefix function · Failure function记录每个前缀的最长真前缀—后缀重合长度的字符串函数。记住“失配之后还能保留多长的已匹配前缀”；Aho–Corasick 把这一思想搬到模式集合上：Trie 同时记住所有模式的所有前缀，失败链接则回答“当前候选走不下去时，次长的候选是谁”。关键图像是状态即匹配进度——自动机始终维护文本当前后缀所能匹配到的最深 Trie 节点，失配时不从头再来，而是退到进度稍浅、但仍然成立的候选上。于是无论模式有多少个，文本只需从左到右读一遍。

取经典模式集 he、she、his、hers，扫描文本 ushers：读 u 停在根；读 s、h、e 依次走到节点 she，在此报告模式 she，且该节点的失败链接指向 he，输出链接使 he 同时被报告；再读 r，节点 she 无 r 边，沿失败链接退到 he 后走 r 边得 her；最后读 s 到达 hers 并报告之。可见较短模式 he 完全藏在失败链上——只报告当前节点自身会漏掉它，这是最常见的实现错误；而逐位置沿失败链逐个上溯又可能把单字符代价拖到与深度成正比，输出链接把这一步压缩到与实际报告数成正比。

空间与转移的表示是另一条边界：显式补全 $\delta$ 得到真正的完整 DFA，每字符 $O(1)$ 转移，但占 $\mathrm{\Theta }(m|\mathrm{\Sigma }|)$ 空间，在大字母表（如 Unicode）下往往浪费；只存 Trie 边加失败链接则空间 $O(m)$，单字符转移为摊还 $O(1)$——沿失败链的下降总量不会超过沿 Trie 边的上升总量。

嵌套模式能更清楚地展示输出链。取模式 a、aa、aaa，扫描文本 aaaa：读到第一个字符时报告 a；第二个位置报告 a 与 aa；第三、第四个位置都分别报告三个、三个模式，因此匹配总数为

自动机的状态转移仍只随文本长度线性增长，但输出这些命中本身就需要 $\mathrm{\Theta }(9)$ 时间；一般复杂度必须写成 $O(|T|+\text{总模式长度}+z)$，其中 $z$ 是实际报告数。空模式会在每个边界位置匹配，重复模式也可能需要分别保留模式编号；只在 Trie 节点上存一个布尔终止标记无法表达这些语义。

Aho–Corasick 是多模式字符串匹配公理库字符串匹配String matching · Exact pattern matching在文本中定位模式串全部出现位置的问题。的标准工具：敏感词过滤、入侵检测的特征扫描、词典与基因序列匹配，都靠它一次扫描文本、同时命中全部模式。把自动机状态当作“当前匹配进度”，还可与动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。组合，解决统计不含任何禁止子串的字符串个数一类问题。失败链接全体构成一棵树（fail 树），在其上做子树统计，能一次性回答“每个模式在文本中出现了多少次”。实现词法分析等任务时，稠密字母表可预填完整转移表，稀疏字母表则需在空间与失败跳转代价之间权衡。

它与静态全文索引解决的是不同工作负载。Aho–Corasick 预处理模式集、随后在线顺序读文本，以上 $O(m+n+z)$ 是常字母表 RAM 下的确定性最坏输出敏感界；后缀树公理库后缀树Suffix tree对加入唯一终止符后的全部后缀构造路径压缩 Trie，并以原文本区间表示边标签。与Burrows–Wheeler 变换公理库Burrows–Wheeler 变换Burrows-Wheeler transform · BWT对带唯一终止符文本的循环移位排序，并取最后一列形成可逆排列。则预处理固定文本以服务许多模式查询。rank/select公理库Rank 与 Select 查询Rank and select在位串上计算前缀频数或定位第 j 次出现，并固定端点和索引约定。把 BWT 变成可导航序列，FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。进一步用压缩自索引换取 count、locate 与 extract 的不同时间—空间成本。选择哪条路线取决于“模式固定还是文本固定”，不能只比较一句笼统的“线性匹配”。