KMP 字符串匹配KMP

利用模式前后缀信息避免重复比较。

核心约束: 失败时保留已经匹配部分中的可复用前缀。
适用问题: 单模式精确字符串匹配。
边界与取舍: 多模式或复杂规则需要不同索引或自动机。

时间与空间#

n 为文本长度，m 为模式长度；按同一种字节或码元比较。

时间复杂度: 预处理 $O(m)$ ，扫描 $O(n)$ ，总 $O(n+m)$
辅助空间: 前缀 / 失败函数实现 $O(m)$

匹配失败时复用前缀信息，不让文本指针回退。若实现为完整 R 字母表 DFA，预处理与空间可达 $O(Rm)$ ，应与前缀函数版区分。

基础原理参考资料

Boost.Algorithm · Knuth–Morris–Pratt预处理、失败回退以及线性匹配。

Princeton · KMP采用字符表 DFA 的另一种实现和空间口径。