KMP 算法

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

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

这个状态还给出正确性不变量。在处理 $T[i]$ 之前，$q$ 是 $T[0..i)$ 的后缀与 $P$ 真前缀的最大重合长度。回退链穷尽可延长的较短候选，字符相等时再延长一位；新值是当前文本前缀与模式的最大重合长度，可能等于 $m$。达到 $q=m$ 就报告起点 $i-m+1$，随后取 $\pi [m-1]$ 恢复“真前缀”的循环入口不变量，从而允许下一次重叠匹配。

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

已读文本的后缀 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理路字典树Trie · Prefix tree按字符串前缀共享路径组织键集合的树形数据结构。 与 Aho–Corasick 自动机会把许多模式前缀合并；这不是把一条 KMP 失败链简单复制多次。

在线性扫描的最坏情形中，这个上界已达最优量级。例如非空全 $a$ 模式与全 $a$ 文本、$m\le n$，任一未检查的字符若改成 $b$，都可能改变应报告的匹配集合，因此精确算法的最坏成本为 $\mathrm{\Omega }(n+m)$。这是最坏输入族的结论；若已知 $m>n$，接口可以直接返回无匹配，无须读完两个串。

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

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

算法选择取决于被预处理的对象。KMP 预处理一个模式并在线读取任意文本；后缀树理路后缀树Suffix tree对加入唯一终止符后的全部后缀构造路径压缩 Trie，并以原文本区间表示边标签。和 FM-index理路FM-indexFM-index · Full-text minute-space index在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。预处理固定全文，以支持许多模式查询，后者还追求压缩空间。把全文索引称为“更快的 KMP”会混淆在线单模式匹配、静态多查询和压缩表示这三个不同目标。