文章目录
KMP 算法详解：从暴力匹配到 O(n+m) 的字符串搜索
字符串匹配是算法面试和工程实践中非常经典的问题：给定一个主串 S 和一个模式串 P，如何在 S 中找到 P 第一次出现的位置？
最直观的做法是暴力匹配，但它在最坏情况下会达到 O(n×m)。KMP 算法通过预处理模式串，把时间复杂度优化到 O(n+m)，并且主串指针全程不回退。
本文从暴力匹配的问题出发，逐步拆解 KMP 的核心思想、next 数组的构建过程以及完整实现。
一、暴力匹配的问题
暴力匹配的思路很简单：从主串的每一个位置开始，逐个字符与模式串比较。如果失配，就把主串指针回退到上一次起点的下一位，模式串指针重置为 0。
例如：
主串 S：A B A B A B C
模式串 P：A B A B C
前四个字符 ABAB 都匹配成功，第 5 个字符失配。暴力做法会把主串指针回退，重新从下一个位置开始比较。
但这里有一个问题：前面已经匹配成功的 ABAB 中，开头 AB 和结尾 AB 是相同的。也就是说，主串中已经走过的部分其实包含了一些“可复用信息”。暴力匹配没有利用这一点，导致大量重复比较。
二、KMP 的核心思想
KMP 的关键在于两件事：
- 主串指针不回退；
- 失配时，模式串指针根据已匹配信息跳转到合适位置。
为了实现第二点，我们需要先对模式串做预处理，得到一张“跳转表”，也就是常说的 next 数组。
三、理解最长相等前后缀
next 数组的基础概念是最长相等前后缀。
- 前缀：字符串中不包含最后一个字符的头部连续子串。
- 后缀：字符串中不包含第一个字符的尾部连续子串。
以模式串 ABABC 为例：
| 子串 | 最长相等前后缀 | 长度 |
|---|---|---|
| A | 无 | 0 |
| AB | 无 | 0 |
| ABA | A | 1 |
| ABAB | AB | 2 |
| ABABC | 无 | 0 |
所以它的前缀表为：
[0, 0, 1, 2, 0]
这个数组的含义是：对于模式串的前 i+1 个字符，它的最长相等前后缀长度是多少。
四、next 数组到底在干什么？
假设当前模式串已经匹配到第 j 个字符时失配，说明 P[0..j-1] 已经和主串中的某段完全匹配。
此时我们不需要从头开始，只需要知道：在这段已匹配的字符串中，有多长的后缀恰好等于模式串的前缀？
这个长度就是 next[j-1]。
因为主串中这段后缀已经匹配成功，而它又等于模式串的前缀，所以模式串可以直接把前缀对齐到这段后缀上，继续比较即可。
换句话说，next 数组回答了一个问题：
失配后，模式串最多能向右滑动多少，同时保证已经匹配的部分不丢失？
五、next 数组的构建过程
构建 next 数组，本质上是让模式串和自己做一次匹配。
我们维护两个指针：
i：当前正在计算的后缀末尾位置；j：当前已知的最长相等前后缀长度，也指向前缀末尾。
初始时：
next[0] = 0;
j = 0;
然后从 i = 1 开始遍历模式串：
for i from 1 to m - 1:
while j > 0 and P[i] != P[j]:
j = next[j - 1];
if P[i] == P[j]:
j++;
next[i] = j;
这里的 while 循环是重点。当 P[i] != P[j] 时，不能直接把 j 设为 0，因为更短的前后缀可能仍然匹配。所以让 j 回退到 next[j-1]，继续尝试。
以模式串 ABABC 为例：
i=1, j=0：B != A，next[1]=0。i=2, j=0：A == A，j=1，next[2]=1。i=3, j=1：B == B，j=2，next[3]=2。i=4, j=2：C != A，j=next[1]=0；C != A，next[4]=0。
最终得到：
next = [0, 0, 1, 2, 0]
六、主串匹配过程
有了 next 数组后，主串匹配就非常清晰了。
int i = 0; // 主串指针
int j = 0; // 模式串指针
while (i < n) {
if (S.charAt(i) == P.charAt(j)) {
i++;
j++;
} else if (j > 0) {
j = next[j - 1];
} else {
i++;
}
if (j == m) {
return i - m; // 匹配成功
}
}
return -1; // 未找到
整个过程只有三种情况：
- 当前字符匹配：
i++，j++； - 失配但
j > 0：模式串指针回退到next[j-1]； - 失配且
j == 0：主串指针i++。
由于主串指针 i 只会向后移动，不会回退，所以主串每个字符最多被访问常数次。
七、复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | O(n + m) |
| 空间 | O(m) |
其中 n 是主串长度，m 是模式串长度。预处理模式串需要 O(m)，主串匹配需要 O(n)。
八、完整代码示例
下面给出一个基于 next 数组的 Java 实现：
public class KMP {
public static int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int n = haystack.length();
int m = needle.length();
int[] next = buildNext(needle);
int i = 0;
int j = 0;
while (i < n) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
} else if (j > 0) {
j = next[j - 1];
} else {
i++;
}
if (j == m) {
return i - m;
}
}
return -1;
}
private static int[] buildNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
九、常见误区
1. next 数组定义不统一
不同资料对 next 数组的定义可能不同：
- 有的从
0开始，表示最长相等前后缀长度； - 有的从
-1开始，表示失配后的跳转位置； - 还有
nextval优化，用于减少模式串内部重复字符带来的无效比较。
理解时不需要死记下标偏移，只要抓住本质：失配后，模式串指针应该跳到哪里，才能复用已匹配信息。
2. 误以为主串指针也要回退
KMP 的优势正是主串指针不回退。模式串指针根据 next 数组跳转，主串指针始终向右移动。
3. 把前缀表理解成“相同子串个数”
最长相等前后缀长度并不是统计有多少个相同子串，而是找最长的、既是前缀又是后缀的子串长度。
十、总结
KMP 算法并不复杂，它的核心只有三步：
- 理解最长相等前后缀；
- 用模式串自身构造
next数组； - 匹配时主串指针不回退，模式串指针按
next数组跳转。 - 口语化表述：“以当前位置结尾的后缀”和“从第一个字母开始的前缀”重合的长度
- “以当前位置结尾的后缀”：不能包含第一个字母，同时要包含当前位置的字母。
它把字符串匹配从“每次失配都重来”优化为“尽可能复用已匹配信息”，从而实现了 O(n+m) 的线性时间复杂度。
掌握 KMP 后，也可以进一步学习 BM 算法、Sunday 算法等更高效的字符串匹配方法。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/m0_46085118/article/details/167589325
