title: KMP tags:

concept
data-structure-and-algorithm
string
joplin type: concept source_type: reconstructed created: 2026-04-22 updated: 2026-04-22 ---

KMP

[!abstract] KMP 是字符串模式匹配算法，核心思想是在失配时利用模式串自身的前后缀信息，避免主串指针回退。

核心机制

预处理模式串得到 next 或 nextVal
匹配失配时调整模式串位置
主串指针不必重新回到已比较过的位置

为什么重要

它体现了“利用已有结构信息减少重复比较”的典型算法思想。
是串匹配中的高频基础概念。

易错点

next 不是“下一个字符下标”，而是失配后模式串该跳到的位置依据。
重点在理解前后缀关系，不在死背模板。

来源

[[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/9.串.md]]

相关页面

[[线性结构]]