一句话总结
朴素匹配在失配时把模式串右移一格、主串指针回退，最坏 O(n×m)。KMP 的核心洞察是：失配时主串指针永不回退，只移动模式串——因为模式串自身的结构（前缀与后缀的重复）已经告诉我们"能直接跳过多少位置"。这个"跳过多少"的信息预先算好，就是 next 数组（部分匹配表）。
🔁
朴素做法的问题
每次失配都让 i 回退到 i-j+1，大量重复比较已确认过的字符。
🎯
KMP 的关键
已匹配的部分本身就是信息：它的最长相等前后缀决定了模式串该滑到哪。
📊
next 数组
只依赖模式串自身，预处理 O(m)，匹配时 O(n)。
⚡
总复杂度
O(n + m)，且主串只需单向扫描一遍，适合流式数据。
一、朴素匹配为什么慢
二、next 数组（部分匹配表）
2.1 定义
next[i] = 模式串 pattern[0..i] 这个子串中，最长的"相等的真前缀与真后缀"的长度。（"真"指不能是字符串本身）
2.2 构造 next 数组（自己匹配自己）
def build_next(pattern):
m = len(pattern)
nxt = [0] * m
nxt[0] = -1 # 约定：0 号位失配，模式整体右移
i, j = 0, -1 # i 扫模式串，j 是当前最长前后缀长度
while i < m - 1:
if j == -1 or pattern[i] == pattern[j]:
i += 1
j += 1
nxt[i] = j # 匹配成功 → 长度 +1
else:
j = nxt[j] # 失配 → j 回退（和匹配主串时完全一样的逻辑）
return nxt
# 另一种常见写法（lps / π 数组，next[i] 直接是最长相等前后缀长度）
def build_lps(pattern):
m = len(pattern)
lps = [0] * m
length = 0 # 当前最长前后缀长度
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length > 0:
length = lps[length - 1] # 回退，不移动 i
else:
lps[i] = 0
i += 1
return lps
三、KMP 匹配主过程
def kmp_search(text, pattern):
if not pattern:
return 0
nxt = build_next(pattern)
i = j = 0 # i 指向主串，j 指向模式串
while i < len(text) and j < len(pattern):
if j == -1 or text[i] == pattern[j]:
i += 1 # ★ 主串指针只前进，永不回退
j += 1
else:
j = nxt[j] # ★ 失配：只回退模式串指针
if j == len(pattern):
return i - j # 匹配成功，返回起始下标
return -1
# 找所有匹配位置
def kmp_find_all(text, pattern):
lps = build_lps(pattern)
res, j = [], 0
for i, ch in enumerate(text):
while j > 0 and ch != pattern[j]:
j = lps[j - 1]
if ch == pattern[j]:
j += 1
if j == len(pattern):
res.append(i - j + 1)
j = lps[j - 1] # 继续找下一个（允许重叠）
return res
复杂度：构建 next 数组 O(m)，匹配 O(n)，总计 O(n + m)，空间 O(m)。
对比朴素匹配的 O(n×m)，在长文本、多模式串场景下差距巨大。
对比朴素匹配的 O(n×m)，在长文本、多模式串场景下差距巨大。
四、应用与扩展
| 场景 / 题目 | 怎么用 KMP 思想 |
|---|---|
| 28 实现 strStr() | KMP 最直接的模板题 |
| 459 重复的子字符串 | 若 n % (n - lps[n-1]) == 0 且 lps[n-1] > 0，则由重复子串构成 |
| 686/1071 重复叠加字符串匹配 | KMP 找最短叠加次数 |
| 1392 最长快乐前缀 | 就是求最长相等前后缀（lps 定义本身） |
| 214 最短回文串 | 用 KMP 找 s+"#"+reverse(s) 的最长前后缀 |
4.1 与其他字符串算法的对比
| 算法 | 预处理 | 匹配 | 特点 |
|---|---|---|---|
| 朴素 BF | O(1) | O(n×m) | 代码最短，短串场景实际很快 |
| KMP | O(m) | O(n) | 主串不回退，适合流式/大文件 |
| Rabin-Karp | O(m) | 均摊 O(n) | 滚动哈希，易扩展到多模式，有哈希冲突风险 |
| Boyer-Moore | O(m) | 均摊优于 O(n) | 从右往左比 + 坏字符/好后缀规则，实际应用（如 grep）常最快 |
| Sunday | O(m) | 均摊 O(n) | BM 的简化版，实现简单 |
| Trie / AC 自动机 | O(总长) | O(n) | 多模式串匹配（KMP 只能单模式） |
💡 工程现实：Python/Java 的
str.find()、indexOf() 内部通常用的是优化过的 Two-Way 或 BM 类算法，实际性能往往优于手写 KMP。KMP 的面试价值在于考察"利用已匹配信息避免重复比较"的思想，以及 next 数组这种"自己匹配自己"的构造技巧——后者在求"最长相等前后缀""循环节"等问题上是不可替代的。
⚠️ 常见错误：
① next 数组定义混乱（0 起始 vs -1 起始），与匹配代码的 j 回退逻辑不匹配 → 死循环或漏匹配；
② 构造 next 时忘记
③ 找所有匹配时，命中后没有把 j 回退到
① next 数组定义混乱（0 起始 vs -1 起始），与匹配代码的 j 回退逻辑不匹配 → 死循环或漏匹配；
② 构造 next 时忘记
j == -1 的特判 → 数组下标越界；③ 找所有匹配时，命中后没有把 j 回退到
lps[j-1] → 漏掉重叠的匹配。