KMP 算法 | Codeboy's Blog

形式陈述

给定文本 $T$ 和非空模式 $P$ ，令 $m=|P|$ ，先计算模式的前缀函数 $\pi$ 。扫描文本时维护状态 $q$ ：已经读过的文本前缀中，最长且等于 $P[0..q-1]$ 的后缀长度。对每个文本字符执行：

text

q = 0
for i = 0, 1, ..., |T| - 1:
    while q > 0 and T[i] != P[q]:
        q = π[q - 1]
    if T[i] == P[q]:
        q = q + 1
    if q == m:
        report i - m + 1
        q = π[m - 1]

最后一行回退而不是清零，使重叠出现也能被报告。预处理耗时 $O(m)$ ，扫描耗时 $O(|T|)$ ，所以总时间为 $O(m+|T|)$ ，额外空间为 $O(m)$ 。空模式应由调用接口单独规定，例如匹配所有边界位置；它不能直接进入上面的 P[q] 访问。

直觉

朴素匹配在失配后把模式起点右移，再从模式首字符重读文本。KMP 保留了已经证明的信息：若当前匹配了 $q$ 个字符，那么已读文本的末尾就是 $P[0..q-1]$ 。发生失配时，一个仍可能成立的较短匹配必须同时是这段模式前缀的后缀和模式自身的前缀，也就是它的 border。 $\pi[q-1]$ 给出最长候选，继续沿 $\pi$ 链回退便按长度依次尝试其他候选。

KMP 在同一文本位置失配后按前缀函数回退模式状态 — KMP 回退 j 而不回退 i

文本下标 $i$ 始终只向右移动。回退的是模式状态 $q$ ，同一个 $T[i]$ 会在必要时与几个候选位置比较，但已经读过的文本字符从不重新作为新的外层输入读取。可把 $q$ 当作势能：成功匹配至多使它增加 $1$ ，每次 while 迭代都使它严格下降。整个扫描中的下降总量受上升总量限制，因此字符比较次数是线性的，而不是每个文本位置都乘上模式长度。

这个状态还给出正确性不变量。在处理 $T[i]$ 之前， $q$ 是 $T[0..i-1]$ 的后缀与 $P$ 前缀的最大重合长度；回退链穷尽所有可能的较短重合，字符相等时再延长一位。于是处理完 $T[i]$ 后不变量继续成立。达到 $q=m$ 时，长度为 $m$ 的后缀只能是一次完整出现，其起点正是 $i-m+1$ 。

例子与边界

取模式 ababaca，其前缀函数是 $[0,0,1,2,3,0,1]$ ；在文本 abababaca 中扫描。读完前五个字符 ababa 后有 $q=5$ 。下一个文本字符是 b，与模式位置 $5$ 的 c 失配，于是回退到

q=\pi[4]=3.

已读文本的后缀 aba 正好也是模式前缀；仍用当前这个 b 与 $P[3]$ 比较即可成功，把 $q$ 推进到 $4$ 。随后读入 a、c、a，最终在文本位置 $8$ 达到 $q=7$ ，报告起点 $8-7+1=2$ 。文本中的 aba 没有被重新读取，只被重新解释为较短的有效前缀状态。

重叠匹配说明了报告后的回退为何必要。模式 aaa 在文本 aaaaa 中出现在位置 $0,1,2$ ；首次匹配后令 $q=\pi[2]=2$ ，下一字符便能延长出第二次匹配。若报告后直接令 $q=0$ ，后两个重叠出现会被漏掉。另一方面，前缀函数记录的是长度，零基代码必须使用 $\pi[q-1]$ ；误用 $\pi[q]$ 可能让状态不缩短，甚至形成死循环。

KMP 解决的是单模式精确匹配。字符相等关系必须稳定，文本流中的每个符号一旦处理便不再回看；若问题允许编辑距离、通配符或完整正则语义，状态需要同时表达更多可能位置，不能只把 == 换成一个宽松谓词。多个模式共享扫描时，Trie 与 Aho–Corasick 自动机会把许多模式前缀合并；这不是把一条 KMP 失败链简单复制多次。

在字符访问模型中，算法至少必须读取所有可能影响答案的文本位置，并读取模式本身，因此 $O(|T|+|P|)$ 在线性量级上已经最优。

推论与应用

KMP 的扫描状态只依赖当前 $q$ 和下一个字符，因此特别适合流式输入。文本可以分块到达，只要在块之间保留 $q$ 和已处理长度，就能跨块报告匹配而无需保存完整文本。前缀函数也可预先编译为“状态 $q$ 读到字符 $c$ 后转向哪里”的有限自动机；当字母表较小且同一模式被反复使用时，这能把每字符的回退循环换成一次表查询，但会增加 $O(m|\Sigma|)$ 的预处理空间。

字符串匹配定义输入与输出，前缀函数提供模式内部的回退结构，KMP 则负责把它变成文本扫描器。周期、border 和前缀出现次数属于前缀函数本身的结构应用；在文本中逐个报告模式出现位置，才是 KMP 的核心职责。

算法选择取决于被预处理的对象。KMP 预处理一个模式并在线读取任意文本；后缀树和 FM-index预处理固定全文，以支持许多模式查询，后者还追求压缩空间。把全文索引称为“更快的 KMP”会混淆在线单模式匹配、静态多查询和压缩表示这三个不同目标。

参考资料

Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt, “Fast Pattern Matching in Strings,” SIAM Journal on Computing 6(2), 1977, pp. 323–350.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Ch. 32.

形式陈述 ​

反向链接

形式陈述