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 完全藏在失败链上——只报告当前节点自身会漏掉它，这是最常见的实现错误；而逐位置沿失败链逐个上溯又可能把单字符代价拖到与深度成正比，输出链接把这一步压缩到与实际报告数成正比。

稠密转移表让每字符只查一次表，但在大字母表下可能浪费空间。只存 $q-1$ 条 Trie 边、失败链接、输出链接与终止编号时，存储为 $O(q+k)$ 个记录。扫描中每次成功沿 Trie 边至多增加一层深度，失败跳转则严格降低深度，因此整段文本共做 $O(n)$ 次孩子字典查询；每次字典查询为常数成本时，才得到 $O(n+z)$。哈希字典通常给期望界，有序字典一般再带 $\log (\sigma +1)$ 因子。这个扫描计费不直接证明稀疏失败表也能线性构建；构建阶段的转移查询须另行分析。

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

自动机的状态转移仍只随文本长度线性增长，但输出这些命中本身就需要 $\mathrm{\Theta }(9)$ 时间；一般复杂度必须写成 $O(|T|+\text{总模式长度}+z)$，其中 $z$ 是实际报告数。空模式在预处理时单独记录，其每个编号都会贡献 $n+1$ 次边界匹配。重复的非空模式共享 Trie 路径，但保留各自编号；只有布尔终止标记无法表达这种逐编号报告。

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

它与静态全文索引解决的是不同工作负载。Aho–Corasick 预处理模式集、随后在线顺序读文本，以上 $O(m+n+z+1)$ 是常字母表 RAM 下的确定性最坏输出敏感界理路输出敏感分析Output-sensitive analysis · Output-sensitive algorithms在明确输出接口后，同时用输入规模与实际输出规模刻画算法运行成本的分析方法。；后缀树理路后缀树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 的不同时间—空间成本。选择哪条路线取决于“模式固定还是文本固定”，不能只比较一句笼统的“线性匹配”。