Aho-Corasick：一遍扫描命中所有 pattern
KMP 用 prefix function 在单个 pattern 上「失配不回退」。要同时找很多 pattern,Aho-Corasick 把它们建成一棵 Trie（见 Trie 一页），再给每个节点加一条 failure link——它正是 prefix function 的多模式版：当前已匹配的串失配时，顺着 fail 跳到「它的最长真后缀所对应的节点」继续，text 指针永不回退。于是把 text 扫一遍，就能把所有 pattern 的所有出现一次找全。
1 · 第一步：给 Trie 连上 failure link
按层 BFS。某节点代表串 S，它的 fail 指向「Trie 里存在的、S 的最长真后缀」对应节点；找不到就指回 root。这与 KMP 里 prefix[j-1] 是同一件事，只是从「一条链」推广到了「一棵树」。虚线箭头就是 failure link（指向 root 的画得淡些）。
dictionary suffix link: 有时一个 pattern 是另一个的后缀（如 he 是 she 的后缀）。顺着 failure link 往回，只要碰到词尾就该「顺便」报告——这条「fail 链上最近的词尾」捷径叫 dictionary link，保证在某个位置结束的每个 pattern 都不漏报。
2 · 第二步：扫描 text
状态 cur 从 root 出发。读到 text[i]：能走 cur 的对应边就走；走不了就顺 failure link 往回跳再试（text 指针 i 不动、不回退）。每到一个状态，顺 dictionary link 把「在此结束」的 pattern 全部报告出来。
复杂度： 不管有多少个 pattern、总长多少，扫描只让 text 的每个字符前进读一次，外加常数次 fail 跳转——总时间 O（text 长度 + 所有 pattern 总长 + 命中数）。它被广泛用于多关键词过滤 / 入侵检测 / 生物序列扫描。
3 · 补全 goto 表：让 fail 跳转彻底消失
上一节的扫描里还留着一个内层循环：走不了当前边时，得顺着 failure link 一跳再跳，直到某个节点有这条边或退回 root。这个循环均摊是 O(1)——每次跳转都让当前深度至少减一，而深度只能靠「前进一格」涨回来——但它终究是循环，每个字符的实际代价并不齐整。
消掉它的办法与 KMP 那页第 3 节如出一辙：把「该退到哪」提前替每一个字符都算好。具体做法是给每个节点补上它在 Trie 里缺失的边——节点
没有字符
的边时，就令 goto[u][c] 直接等于 goto[u.fail][c]，即「
的最长真后缀读到
会去哪，
就去哪」。root 是唯一的例外：它的缺边指回自己，保证读到任何字符都不会掉出自动机。
补完之后，每个（节点，字符）恰好一个去向，Trie 就从一台带回退的自动机变成了一台完全 DFA，扫描退化成一行 cur = goto[cur][c]。
这正是 KMP 建表那一步的多模式版。 KMP 里状态
的失配各列整列抄自重启状态
（dfa[c][j] = dfa[c][X]），因为二者面对同一个「最长已匹配后缀」；节点
的缺边整格抄自它的 fail 节点（goto[u][c] = goto[u.fail][c]），理由一字不差。fail 节点就是
——单模式时 Trie 退化成一条链，
和 fail 节点是同一个东西。
补全还有一个附带好处：建表时子节点的 fail 也只需一次查表（v.fail = goto[u.fail][c]），第 1 节那个「没有 u.ch 边就沿 fail 继续」的 while 循环一并消失——建表和扫描双双变成无内层循环的直线代码。
代价是空间。 fail 链版本每个节点只存一个指针，总空间 O(节点数)；补全版要存满整张表，O(节点数 × |Σ|)。ASCII 字母表（|Σ|=256）下这就是两个数量级的差距，中文或 Unicode 词表更不必谈。
所以生产实现按场景取舍：Snort / Suricata 这类 IDS、DPI 设备的特征匹配吃的是确定的每字符延迟，字母表又固定在 256，通常直接补全；词表巨大或字母表很宽时，则退回 fail 链，或改用 double-array trie、位图压缩等把稀疏的转移表压回可接受的大小。敏感词过滤那页的 demo 走的是 fail 链版本——词表是中文，补全并不划算。