KMP 字符串匹配
字符串 · 失配跳转不回退
在文本里找模式串
在一段文本 T（abababcab）里找模式串 P（ababc）第一次出现的位置——这是编辑器「查找」、grep、DNA 比对的基本操作。朴素做法：把 P 对齐到 T 的每个位置逐字符比，一旦失配就把 P 整体右移一格、从头再比——最坏 O(n·m)，因为每次失配都白白丢掉了已经比对成功的信息。
KMP：失配时「跳」而不是「重来」
KMP 的洞见：失配时，已经匹配的那段前缀我们是知道的，不必从头再比。它预先算出模式串的部分匹配表（lps，又叫失败函数 π）：lps[k] 是 P[0..k] 里「既是真前缀又是真后缀」的最长长度。
匹配时用两个指针：i 扫文本、j 扫模式。字符相等，i、j 一起前进；失配时，文本指针 i 绝不回退，只把 j 跳到 lps[j-1]——相当于把模式串向右滑动，让「已匹配前缀的最长可复用后缀」接着比。这样每个文本字符最多被看常数次，总复杂度降到 O(n + m)。
下面是 T=abababcab、P=ababc（其 π = [0,0,1,2,0]）。点「下一步」逐步看：T 行在上、P 行按对齐位置滑动、π 行是部分匹配表。当前比较的两格琥珀高亮，已匹配的前缀变绿；比到 abab 后 a≠c 失配，j 用 π 跳回、模式右滑（留意 i 没动！），接着一路匹配到 ababc——命中于下标 2。右侧代码随每一步同步高亮。
T
a
b
a
b
a
b
c
a
b
P
a
b
a
b
c
π
0
0
1
2
0
在文本 T 中找模式 P：i、j 都从 0 开始，模式对齐到文本开头
为什么快
朴素匹配失配后 i 回退、模式从头比，同一段文本被反复扫描。
KMP 靠部分匹配表让 i 永不回退，模式串「聪明地滑动」，跳过注定失配的对齐——O(n+m)。
部分匹配表本身也用「模式串和自己匹配」的方式
KMP 靠部分匹配表让 i 永不回退，模式串「聪明地滑动」，跳过注定失配的对齐——O(n+m)。
部分匹配表本身也用「模式串和自己匹配」的方式
O(m) 算出（本页预置展示，构建过程同样精巧）。 KMP 是字符串匹配的基石。同一族里还有：Rabin-Karp（滚动哈希）、Boyer-Moore（从右往左比 + 坏字符/好后缀跳更远）、以及多模式的 AC 自动机——都是「用预处理换匹配时的跳跃」这一思想的不同展开。