形式陈述

先把所有模式插入 Trie。对每个节点 $v$，失败链接 $\mathrm{fail}(v)$ 指向其字符串的最长真后缀、且该后缀也是 Trie 前缀的节点；按 BFS 构造。 扫描文本时，缺失转移沿失败链接回退，或预先补成完整 DFA 转移。到达节点时，该节点及其输出链接祖先所对应的模式均在当前位置结束。 构建与扫描时间通常为 $O(\text{模式总长}+\text{文本长}+\text{报告数})$。

直觉

Trie 记住所有模式前缀，失败链接把 KMP 的“最长可继续后缀”同时扩展到多模式集合。

例子与边界

模式 he, she, hers 共享前缀和后缀状态。只报告当前节点自身会漏掉沿失败链结束的较短模式；大字母表下显式补全全部转移可能浪费空间。

推论与应用

用于多模式检索、敏感词扫描、字典匹配和带自动机状态的动态规划。

参考资料

• Alfred V. Aho, Margaret J. Corasick, Efficient String Matching: An Aid to Bibliographic Search (1975), original multiple-pattern algorithm.
• OI-Wiki contributors, OI-Wiki (2026), Aho–Corasick automaton.