文本ababa中，模式aba出现在起点0和2。第一次匹配成功以后，已经读过的后缀a同时也是模式的前缀。如果把状态清零，就会漏掉第二次匹配；如果重新从每个起点比较，又重复使用了已经确定的信息。

KMP用模式的前后缀关系保存这部分信息。多个模式组成Trie以后，同一种后缀关系扩展为Aho–Corasick的失败链接。两者都让文本位置只向前移动，状态则允许回退。

输入和输出先固定

文本T长度为n，单个模式P长度为m。多模式输入是有序列表，模式数k、总长度L；重复字符串保留不同的输入ID。字符比较和数组索引先按单位成本计算，Python实现的位置是Unicode码点下标，不是UTF-8字节偏移，也不是用户可见字形编号。组合字符不自动归一化。

kmp_find(text, pattern)返回所有匹配起点，升序排列且保留重叠。空模式抛出ValueError，空文本对非空模式返回空列表。辅助函数prefix_function('')允许返回空表，这不改变匹配接口的空模式约定。

AhoCorasick(patterns).find(text)返回(起点, 模式ID)。顺序先按结束位置递增，同一结束位置先长模式后短模式，同一个模式字符串的ID按输入顺序排列。这里不额外排序全部结果；若调用者要求按起点排列，要另计排序成本。空模式列表合法，其中包含空字符串则拒绝。

前缀函数为何足以回退

定义π[i]为P[0:i+1]的最长真前缀与后缀的公共长度。“真”排除整个字符串，所以π[i]≤i。以ababa为例，π为[0,0,1,2,3]。

处理文本下一个字符前，状态j表示：已读文本的后缀与P的长度j前缀相等。如果新字符不等于P[j]，可能继续匹配的较短前缀必须同时是P[0:j]的后缀，因此回退到π[j−1]。继续失配就沿同样的链下降。链列举所有仍可能成立的边界，不会跳过正确候选；降到0仍不相等时，这个字符不能结束任何非空前缀。

字符相等便令j增加1。达到m时报告起点，再回退到π[m−1]，保存完整匹配中的可复用后缀。这个回退直接给出开头的重叠结果。

构建π表使用同一条回退规则。随着扫描位置向右，j每轮至多增加1，失败回退严格减小j；所有下降次数由此前增长次数支付。因此构建表最坏O(m)，扫描文本最坏O(n)，加上返回值存储O(z)，总空间O(m+z)。这是对任意输入的确定性总界；把下降次数摊到整个扫描不等于“只有平均输入才线性”，也没有引入随机假设。

这里采用常见的前缀函数版KMP名称。Helsinki讲义把普通border回退版称为MP，把进一步跳过必然失配候选的优化失败函数称为KMP；名称不同不改变本文实际给出的回退规则与线性界。

Trie保存前缀，失败链接保存后缀

Trie每条边标一个字符，根到节点的路径表示一个模式前缀。完整模式终点存自己的ID列表。contains(word)必须走完整个词并检查终点ID；路径存在只表示它是前缀，不能据此判定完整词存在。

AC的fail[v]指向节点v路径字符串的最长真后缀，且这个后缀也在Trie中。根的失败状态是根。构建时按BFS处理：父节点的失败链接已经确定，给孩子寻找失败状态时，从父节点的失败状态开始尝试同字符转移，失败再沿链接下降。

查询不变量变为：当前节点表示已读文本的最长后缀，并且它是某个模式的前缀。新字符可转移就前进，不可转移就沿失败链接寻找较短候选；根仍无边时保持根。与KMP相同，较短候选必须位于后缀链，因而没有漏掉可能的匹配。

不过，当前状态不一定包含所有输出。模式为he和she、文本为she时，当前节点表示she，后缀he也应报告。只检查当前节点是否终结会漏报。

输出链把报告成本归入z

每个节点保存一个输出链接，指向失败链上最近的终结节点。令u=fail[v]：若u终结，输出链接为u；否则复用u的输出链接。BFS保证这些信息已经计算完毕。

读完一个字符后，先报告当前节点自己的ID，再沿输出链接报告后缀模式。输出链只用于报告，不修改下一轮使用的搜索状态。每次跳转至少产生一个结果，因此链遍历能计入输出数量z。

模式a, aa, …, a^r在文本a^r中有r(r+1)/2个匹配。即使转移只花线性时间，返回这些结果也需要二次时间和空间。把每个节点所有祖先输出列表提前复制下来，还会在查询之前引入不必要的存储增长；本实现每个模式ID只存一次。

字典表示决定复杂度前提

令V为Trie节点数，V≤L+1。常数字母表可以给每个节点分配定长转移数组；字母表大小σ变化时，初始化与空间须显式计入Vσ。稀疏转移避免为不存在的边分配槽位，但访问成本取决于字典实现。

Python教学实现使用dict。查询主状态每读一个字符至多深入一层，失败跳转严格降低深度，全部失败跳转O(n)。在字典操作期望O(1)的假设下，查询期望O(n+z)，保存Trie、失败链接、输出链接和ID共O(L+k)，另加返回值O(z)。这不是字典访问的无条件最坏常数保证，也没有给出高概率尾界。

构建也可按总模式长度计费，但分析顺序不必等于BFS执行顺序。沿一条模式路径，令d_i为第i个节点的失败目标深度，w_i为计算该边时的失败跳转数。每跳一次至少降一层，最后成功转移至多加一层，所以w_i≤d_{i−1}+1−d_i。沿整条路径求和，失败次数至多模式长度。所有Trie边至少属于一条模式路径，重复覆盖只放大非负成本，因此全体失败跳转至多O(L)。配合BFS、稀疏边和输出链接，字典期望常数假设下构建期望O(L+1)；空字典的根节点解释其中的常数项。

可复跑教学检查

实现位于examples/advanced-algorithms/string_match.py，与前文一致使用标准库和独立朴素参照。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_string_match.py

参照直接在每个文本起点调用startswith，再按约定顺序排列命中，不调用KMP或失败链接。二元字符表上枚举长度至多6的文本、长度1到3的模式；AC字典枚举零到两个模式，允许重复。

本次实际执行通过1778次KMP查询、26797次AC查询、6541次完整词查询，覆盖211个字典；另有Unicode、重叠、空文本、空字典和空模式拒绝检查。结果记录在examples/advanced-algorithms/results/string_match.json。64个逐渐增长的a模式只占65个Trie节点、64个存储ID，在64个a上输出2080个匹配。

这些是有限差分检查和教学实现的计数，不是一般正确性证明，也没有测量吞吐量。若把Unicode等价形式、流式分块状态或正则表达式引入接口，需要另定义语义；当前实现不提供这些行为。

练习

  1. 对文本aaaaa、模式aaa写出每次报告后的j。说明改成j=0会漏掉哪些起点，并用π表解释保留状态的正确性。
  2. 模式为['he','she','he']，文本为she。列出按本文接口排序的全部结果，画出搜索失败链接与输出链接，说明重复ID为何计入z。

参考资料