How is Aho–Corasick different from just running KMP once per pattern?

Running KMP separately for k patterns over a text of length n costs O(k·n) in the worst case, since each pattern requires its own pass. Aho–Corasick merges all patterns into one automaton and scans the text exactly once, costing O(n + m + z) regardless of how many patterns there are, which is far faster when searching for hundreds or thousands of patterns simultaneously.

What exactly is a failure link, and why is it needed?

A failure link from node v points to the trie node representing the longest proper suffix of v's string that is still a prefix of some pattern. When the automaton can't extend the current match with the next character, it follows failure links instead of restarting from the root, so no input character is ever re-read — this is what keeps the scan linear in the text length.

Can Aho–Corasick find overlapping matches, like both "he" and "hers" ending near the same position?

Yes. Because each trie node stores a merged output set gathered by following failure links up to the root (the dictionary suffix chain), a single state can report multiple patterns that are suffixes of one another or that simply end at the same text position, so all overlapping and nested matches are reported correctly.

Where is Aho–Corasick used in practice?

Beyond its original use in the Unix fgrep utility, it powers antivirus engines matching files against large signature databases, network intrusion detection systems scanning packets for known attack strings, spam and content filters, and bioinformatics tools searching DNA sequences for many short motifs at once.

首页▸算法与人工智能▸Aho–Corasick — 多模式字符串搜索

🔤 Aho–Corasick — 多模式字符串搜索

构建包含多个模式和失败链接的字典树,然后以单次 O(n) 扫描文本,观察自动机如何沿失败链接跳转并一次性报告每个匹配。

算法与人工智能2D高级60 FPS

关于 Aho–Corasick

Aho–Corasick 算法由 Alfred V. Aho 和 Margaret J. Corasick 于1975年在贝尔实验室发明,解决了多模式字符串匹配问题:给定一个模式字典和一段文本,在单次线性扫描中找出每个模式的每一次出现。它将 Knuth–Morris–Pratt(KMP)算法从单一模式推广到多个模式,方法是将所有模式合并到一棵共享字典树中,并通过广度优先遍历计算失败链接,正如 KMP 为单个模式计算失败函数一样。每个节点的失败链接指向其字符串的最长真后缀,该后缀同时也是某个模式的前缀,每个节点还携带一个沿失败链接一路追溯到根节点而收集来的合并「字典后缀」输出集。这样一来,扫描长度为 n 的文本只需 O(n + m + z) 的代价,其中 m 是所有模式的总长度,z 是报告的匹配数量。由于这种效率,Aho–Corasick 是最初的 fgrep/grep -F 工具、能同时对照数千个恶意软件特征码检查文件的杀毒软件扫描器,以及实时检查数据包载荷中已知攻击字符串的网络入侵检测系统的基础。

常见问题

Aho–Corasick 与对每个模式各运行一次 KMP 有何不同?

对长度为 n 的文本分别为 k 个模式各运行一次 KMP,最坏情况下代价为 O(k·n),因为每个模式都需要单独一趟扫描。Aho–Corasick 将所有模式合并成一个自动机,只需扫描文本恰好一次,无论有多少个模式,代价都是 O(n + m + z),这在同时搜索成百上千个模式时快得多。

失败链接究竟是什么,为什么需要它?

节点 v 的失败链接指向字典树中代表 v 的字符串的最长真后缀、且该后缀仍是某个模式前缀的节点。当自动机无法用下一个字符扩展当前匹配时,它会沿失败链接跳转,而不是从根节点重新开始,因此没有任何输入字符会被重新读取——这正是使扫描相对文本长度保持线性的原因。

Aho–Corasick 能找到重叠的匹配吗,比如「he」和「hers」在同一位置附近结束?

可以。由于每个字典树节点都存储了一个沿失败链接一路追溯到根节点(字典后缀链)收集而来的合并输出集,单个状态就可以报告多个互为后缀的模式,或者只是恰好在同一文本位置结束的模式,因此所有重叠和嵌套的匹配都能被正确报告。

Aho–Corasick 在实践中用在哪里?

除了最初在 Unix fgrep 工具中的应用外,它还驱动着对照庞大特征码数据库匹配文件的杀毒引擎、扫描数据包中已知攻击字符串的网络入侵检测系统、垃圾邮件与内容过滤器,以及一次性在 DNA 序列中搜索大量短基序的生物信息学工具。

⚙ Under the hood

Build a trie of several patterns plus failure links, then scan text in a single O(n) pass, watching the automaton follow failure links and report every match at once.

algorithmsstring matchingtrieautomatoncomputer science

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install