第21章：字符串中查找子串位置（KMP）：next数组计算与匹配过程
字符串查找，说白了就是在一个大串里找一个小串。
你可能会说：“这还不简单？暴力匹配，一个字符一个字符比呗！”
没错，暴力法确实能解决问题。但你想过没有——如果主串是几百万字符，模式串也有几万字符，暴力法会怎样？它会反复回溯，把已经比较过的字符再比一遍。效率？惨不忍睹。
我早年做文本编辑器的时候，就吃过这个亏。用户搜索一个长词，程序卡了好几秒。后来我换上了KMP算法，搜索速度直接起飞。今天我就把KMP算法的核心——next数组的计算和匹配过程，给你掰开了讲清楚。
21.1 暴力匹配的问题在哪？
先看一个简单例子。
主串：ABABABCABABABC
模式串：ABABABC
暴力匹配的做法是：从主串第0位开始，逐个比较。如果某一位不匹配，模式串整体右移一位，再从模式串第0位开始比。
这样做有什么问题？
我举个例子你就明白了。假设模式串是ABABABC，主串是ABABABDABABABC。
暴力匹配时，前6个字符ABABAB都匹配上了，第7个字符主串是D，模式串是C，不匹配。于是模式串右移一位，又从A开始比。
但你想过没有——我们已经知道主串前6个字符是ABABAB，模式串前6个字符也是ABABAB。模式串右移一位后，其实有一部分字符是肯定能匹配上的，根本不需要重新比较。
暴力法偏偏就重新比较了。这就是它慢的原因。
核心思想：KMP算法的精髓就是——利用已经匹配过的信息，不让模式串回溯到开头，而是跳到下一个可能匹配的位置。
21.2 next数组是什么？
next数组，也叫部分匹配表（Partial Match Table）。它记录了模式串中每个位置之前的子串的最长相等前后缀长度。
什么叫前后缀？
- 前缀：除了最后一个字符外，一个字符串的所有头部子串。
- 后缀：除了第一个字符外，一个字符串的所有尾部子串。
举个例子：字符串ABAB
- 前缀：
A、AB、ABA - 后缀：
B、AB、BAB - 最长相等前后缀：
AB，长度为2
next数组的值，就是每个位置之前的子串的最长相等前后缀长度。
注意：next数组通常有两种定义方式。我习惯用next[i]表示模式串前i个字符（即下标0到i-1）的最长相等前后缀长度。这样next[0] = -1，next[1] = 0。
我的习惯：next[0] = -1，next[1] = 0。这样在匹配时，如果模式串第0位就不匹配，直接让模式串右移一位，主串指针前进一位。逻辑非常清晰。
21.3 next数组的计算过程
计算next数组，本质上是在模式串内部做一次“自我匹配”。
我们用一个例子来走一遍。模式串：ABABABC
先初始化：
- next[0] = -1
- next[1] = 0
然后从i=2开始，逐个计算next[i]。
计算next[2]：前2个字符是AB，前缀有A，后缀有B，没有相等的前后缀，所以next[2] = 0。
计算next[3]：前3个字符是ABA，前缀有A、AB，后缀有A、BA。最长相等前后缀是A，长度为1，所以next[3] = 1。
计算next[4]：前4个字符是ABAB，前缀有A、AB、ABA，后缀有B、AB、BAB。最长相等前后缀是AB，长度为2，所以next[4] = 2。
计算next[5]：前5个字符是ABABA，最长相等前后缀是ABA，长度为3，所以next[5] = 3。
计算next[6]：前6个字符是ABABAB，最长相等前后缀是ABAB，长度为4，所以next[6] = 4。
计算next[7]：前7个字符是ABABABC，最长相等前后缀是0（因为最后一个字符C破坏了连续性），所以next[7] = 0。
最终next数组：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 模式串 | A | B | A | B | A | B | C | |
| next[i] | -1 | 0 | 0 | 1 | 2 | 3 | 4 | 0 |
你看，next数组的值并不是单调递增的。当遇到不匹配的字符时，它会跳回0。
21.4 计算next数组的代码实现
直接上代码。这是我个人比较喜欢的写法，简洁且不容易出错。
void getNext(const char *pattern, int *next) {
int len = strlen(pattern);
next[0] = -1;
int i = 0, j = -1;
while (i < len - 1) {
if (j == -1 || pattern[i] == pattern[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}这段代码的核心逻辑是什么？
i是当前要计算next值的下标，j是前一个位置的最长相等前后缀长度。如果pattern[i] == pattern[j]，说明可以扩展，next[i+1] = j+1。如果不相等，j就回退到next[j]，继续尝试。
我曾经踩过的坑：一开始我写next数组计算时，没有处理j == -1的情况。结果在回退时，j变成了-1，然后访问pattern[j]直接数组越界。所以一定要记住：j == -1时，说明已经回退到开头了，直接让i++，j++，next[i] = 0。
21.5 KMP匹配过程
有了next数组，匹配过程就简单了。
我们用两个指针：i指向主串，j指向模式串。
- 如果主串[i] == 模式串[j]，i++，j++
- 如果不相等，j = next[j]（模式串向右滑动）
- 如果j == -1，i++，j++（模式串开头都不匹配，主串前进一位）
- 如果j == 模式串长度，说明匹配成功，返回i - j
还是用刚才的例子：主串ABABABDABABABC，模式串ABABABC。
匹配过程如下：
- i=0, j=0: A==A, i=1, j=1
- i=1, j=1: B==B, i=2, j=2
- i=2, j=2: A==A, i=3, j=3
- i=3, j=3: B==B, i=4, j=4
- i=4, j=4: A==A, i=5, j=5
- i=5, j=5: B==B, i=6, j=6
- i=6, j=6: D != C, j = next[6] = 4
- i=6, j=4: D != A, j = next[4] = 2
- i=6, j=2: D != A, j = next[2] = 0
- i=6, j=0: D != A, j = next[0] = -1
- i=7, j=0: A==A, i=8, j=1
- ...继续匹配，直到j=7，匹配成功
你看，当遇到不匹配时，模式串没有回溯到开头，而是跳到了next[j]的位置。这就是KMP快的原因。
21.6 KMP匹配的代码实现
int kmpSearch(const char *text, const char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
if (m == 0) return 0;
int next[m];
getNext(pattern, next);
int i = 0, j = 0;
while (i < n && j < m) {
if (j == -1 || text[i] == pattern[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == m) {
return i - j; // 匹配成功，返回起始位置
} else {
return -1; // 匹配失败
}
}这段代码很简洁。你注意看，匹配循环里只有两种情况：要么匹配成功，i和j都前进；要么匹配失败，j回退到next[j]。没有多余的判断。
我的建议：在实际项目中，如果你只需要查找一次，KMP可能不是最优选择。因为计算next数组本身也有开销。但如果要反复查找同一个模式串（比如文本编辑器中的“查找全部”），KMP的优势就非常明显了。
21.7 用SVG图理解KMP核心逻辑
下面这张图展示了KMP匹配的核心流程。我画了三个关键阶段：初始化、匹配成功、匹配失败回退。
21.8 避坑指南：我踩过的三个坑
坑一：next数组下标越界
我曾经在计算next数组时，没有处理好j == -1的情况。当模式串中连续多个字符都不匹配时，j会一直回退到-1。如果不加判断，访问pattern[j]就会越界。解决方案就是在循环条件中加上j == -1的判断。
坑二：next数组定义混淆
不同教材对next数组的定义不一样。有的从0开始，有的从1开始。有的next[i]表示前i个字符的最长相等前后缀长度，有的表示前i-1个字符。我建议你固定一种写法，不要混用。我个人习惯用next[0] = -1，next[1] = 0这种。
坑三：模式串长度大于主串
这个其实不算KMP的问题，但我在项目中确实遇到过。用户输入了一个很长的搜索词，主串反而很短。这种情况下，KMP的next数组计算开销可能比暴力匹配还大。所以实际使用时，可以先判断一下长度，如果模式串比主串长，直接返回-1。
21.9 总结
KMP算法的核心就两件事：
- 计算next数组：找出模式串每个位置的最长相等前后缀长度
- 利用next数组匹配：匹配失败时，j回退到next[j]，而不是0
说白了，KMP就是“吃一堑，长一智”。每次匹配失败，它都记住了之前匹配成功的信息，下次不再重复比较。
我当年在文本编辑器中用上KMP后，搜索响应时间从秒级降到了毫秒级。那种感觉，就像给程序装上了涡轮增压。希望你也能体会到这种快感。
一句话记住KMP：匹配失败时，模式串不是从头再来，而是跳到下一个可能匹配的位置。
公众号：蓝海资料掘金营，微信deep3321