专题进阶 · 字符串算法推荐总顺序 · 第 88 / 148 课

在 Trie 上添加失败链接,让一次文本扫描同时发现多个模式。

先学会这些,再进入本课 字典树 KMP 广度优先搜索
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 字符串算法

AC 自动机Aho–Corasick

在 Trie 上增加失败链接,一次扫描匹配多个模式串。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

在 Trie 上添加失败链接,让一次文本扫描同时发现多个模式。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

模式为 he、she、his、hers,扫描 'ushers',怎样同时找到 she、he 与 hers?

02一步步得到方法

Trie 状态表示已经匹配的前缀

每个节点对应某个模式前缀。读到字符后若有边就前进;没有边时,不能直接完全重启,因为当前字符串的某个后缀可能仍是另一模式的前缀。

fail[v] 指向当前前缀的最长真后缀对应的 Trie 节点,思想类似 KMP 边界。沿失败链寻找有当前字符出边的状态,找不到就回根。

用 BFS 构造失败关系

根的直接孩子 fail 都是根。按深度递增处理节点 v 的字符边 c→u,从 fail[v] 开始寻找能接 c 的后缀状态,得到 fail[u]。浅层 fail 已完成,才能正确构造深层。

到达 she 的终止节点时,失败链还指向 he 的终止节点,因此应同时报告两个模式。本教学实现把失败节点的输出列表复制到当前节点,容易理解,但大量嵌套模式下可能增加预处理空间。

失败链接让多模式共享失配信息

Trie 边代表继续匹配当前前缀,失败链接指向当前字符串最长的、仍是某个模式前缀的真后缀。失配时沿失败链接回退,可以保留已经读到的文本信息。

匹配结果不仅来自当前节点的终止标记,也可能来自失败链上的较短模式。例如某个长模式结束时,作为其后缀的短模式也同时结束;构建或查询时需要正确传播输出。

03把一个小例子完全算清楚

模式 he、she、his、hers;文本 ushers。

步骤计算与状态为什么这样做
读 u、s、hu 回根,随后走到 sh维持最长可用前缀
读 e到 she,报告 she 和后缀 he输出继承
读 rshe 无 r,失败到 he,再走 her复用后缀
读 s报告 hers,起点 2没有重新扫描文本

窄屏可左右滑动表格,阅读完整计算与理由。

输出可能在同一文本位置包含多个匹配,也允许重叠。

04为什么这个方法成立

  1. 失败链接选择当前已读文本中仍可作为模式前缀的最长后缀。
  2. 失配沿更短后缀尝试,不会丢掉任何可能结束于未来位置的匹配。
  3. 输出列表包含当前终止模式及失败后缀终止模式,因此所有结束于当前位置的匹配被报告。

05把推导翻译成代码

Python · 可独立运行的教学实现

from collections import deque
def aho_find(text,patterns):
    assert all(patterns)
    go,fail,out = [{}],[0],[[]]
    for index,p in enumerate(patterns):
        node = 0
        for c in p:
            if c not in go[node]:
                go[node][c] = len(go)
                go.append({}); fail.append(0); out.append([])
            node = go[node][c]
        out[node].append(index)
    q = deque(go[0].values())
    while q:
        v = q.popleft()
        for c,u in go[v].items():
            f = fail[v]
            while f and c not in go[f]:
                f = fail[f]
            fail[u] = go[f].get(c,0)
            out[u].extend(out[fail[u]])
            q.append(u)
    node, result = 0,[]
    for i,c in enumerate(text):
        while node and c not in go[node]:
            node = fail[node]
        node = go[node].get(c,0)
        for p in out[node]:
            result.append((i-len(patterns[p])+1,p))
    return result

逐个理解关键决定

out[u].extend(out[fail[u]])
继承后缀模式,确保 she 结束时也报告 he。
i-len(patterns[p])+1
由结束位置换算每个模式自己的起点,不能用当前 Trie 深度统一计算。

06时间、空间与实现范围

文本扫描在字典操作平均 O(1) 下为 O(N+Z),Z 为输出匹配数。

本稀疏教学构建有失败链查找和输出列表复制,最坏成本受 Trie 深度及继承输出总量影响,不能简单承诺总模式长度线性。工程版可补全转移、使用输出链接,控制这些成本。

07改变条件,检查哪里会出错

匹配到一个模式就重置根

会漏掉重叠与共享后缀模式。

声称每字符最多输出一个结果

多个模式可在同一位置结束,输出规模必须单独计入。

只输出当前 Trie 节点自己的单词

会漏掉作为当前匹配后缀的其他模式,需考虑失败链接上的输出。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

模式 a、aa,文本 aaa 匹配几次?

需要一点提示

按每个结束位置列出。

查看解析与答案

a 三次,aa 两次,共 5 次。

练习 2 · 边界与辨析

为什么按深度而非任意顺序建 fail?

需要一点提示

深层依赖父节点 fail。

查看解析与答案

BFS 保证父节点及更短后缀状态已经构建完成。

练习 3 · 变式与迁移

模式很多且输出密集时,怎样避免复制巨大 out 列表?

需要一点提示

只记录可追溯的终止后缀。

查看解析与答案

使用输出链接指向下一个终止节点,扫描时按实际匹配遍历,避免在每个节点复制全部祖先输出。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 字符串算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。