形式陈述

KMP 在文本 $T$$T$ 中查找模式 $P$$P$。预处理前缀函数 $\pi[q]$$\pi [q]$：$P[0..q]$$P[0..q]$ 的最长真前缀且同时为后缀的长度。匹配到 $q$$q$ 个字符后若下一个失配，不回退文本位置，而令 $q\leftarrow\pi[q-1]$$q\leftarrow \pi [q-1]$，重复直到可继续。预处理与扫描各为线性时间，总时间 $O(|P|+|T|)$$O(|P|+|T|)$、额外空间 $O(|P|)$$O(|P|)$。正确性依赖已匹配后缀必等于模式某前缀，前缀函数枚举其最长候选。

直觉

失配时，已经读过的文本并非全部作废；模式自身的前后缀重叠告诉我们哪些字符仍可作为下一次匹配开头。

例子与边界

模式 ababaca 在匹配 ababa 后失配，可利用后缀 aba 等于前缀 aba 跳到长度 3，而非从头开始。前缀必须是真前缀，否则会原地循环。KMP 处理单模式精确匹配；多个模式更适合 Aho–Corasick，近似匹配也需其他算法。字符比较模型下线性时间最优到常数，因为至少要读取文本。实现中 0/1 基索引和 $\pi$$\pi$ 定义差一是常见错误。

推论与应用

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，Parts I–VI。