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、h | u 回根,随后走到 sh | 维持最长可用前缀 |
| 读 e | 到 she,报告 she 和后缀 he | 输出继承 |
| 读 r | she 无 r,失败到 he,再走 her | 复用后缀 |
| 读 s | 报告 hers,起点 2 | 没有重新扫描文本 |
窄屏可左右滑动表格,阅读完整计算与理由。
输出可能在同一文本位置包含多个匹配,也允许重叠。
04为什么这个方法成立
- 失败链接选择当前已读文本中仍可作为模式前缀的最长后缀。
- 失配沿更短后缀尝试,不会丢掉任何可能结束于未来位置的匹配。
- 输出列表包含当前终止模式及失败后缀终止模式,因此所有结束于当前位置的匹配被报告。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
模式 a、aa,文本 aaa 匹配几次?
需要一点提示
按每个结束位置列出。
查看解析与答案
a 三次,aa 两次,共 5 次。
为什么按深度而非任意顺序建 fail?
需要一点提示
深层依赖父节点 fail。
查看解析与答案
BFS 保证父节点及更短后缀状态已经构建完成。
模式很多且输出密集时,怎样避免复制巨大 out 列表?
需要一点提示
只记录可追溯的终止后缀。
查看解析与答案
使用输出链接指向下一个终止节点,扫描时按实际匹配遍历,避免在每个节点复制全部祖先输出。