【新手向】理解KMP算法

前言

本文仅作为小白学习算法时的复习。

一、 为什么我们需要KMP？

在讲解KMP之前，我们先看看普通人是怎么做字符串匹配的（也就是暴力破解法 Brute Force）。

假设要在主串 text = "ABABCABAA" 中找模式串 pattern = "ABACA"。

暴力法的逻辑是：主串和模式串一个字符一个字符对比，如果匹配失败，主串就退回到刚才开始的下一个位置，模式串退回到起点，重新开始对比。

暴力法的痛点：每次匹配失败，主串的指针都要“倒车”（回溯）。如果遇到很多重复的字符，时间复杂度会飙升到 O(m x n)。

KMP算法的诞生，就是为了解决“倒车”问题。 它的核心思想是：主串的指针永远不回溯，每次匹配失败时，利用已经匹配过的信息，让模式串尽可能多地往右滑动。时间复杂度直接降到了 O(m + n)！

二、 KMP的灵魂：最长公共前后缀

要让模式串知道每次匹配失败后该往右滑动多少，我们需要引入KMP的灵魂概念——前后缀。

• 前缀：包含首字母，但不包含尾字母的所有子串。

• 后缀：包含尾字母，但不包含首字母的所有子串。

以字符串 "ABABA" 为例：

• 前缀有：A, AB, ABA, ABAB

• 后缀有：A, BA, ABA, BABA

• 它的最长公共前后缀就是 "ABA"，长度为 3。

这有什么用呢？

假如我们在主串中匹配到了 "ABABA"，但下一个字符匹配失败了。因为我们知道 "ABABA" 的前 3 个字符和后 3 个字符是一模一样的（都是 "ABA"）。所以我们不需要从头再来，直接把模式串开头的 "ABA" 对齐到刚才匹配的末尾 "ABA" 就可以了！

三、 揭秘 next 数组（前缀表）

为了记录模式串中每个位置的“最长公共前后缀长度”，我们把它存进一个数组里，这个数组在KMP中通常被称为 next 数组（或者叫 lps / 前缀表）。

对于模式串 pattern = "ABABC"，它的 next 数组计算如下：

匹配规则：

当我们在某个字符处匹配失败时，看它前一个字符的 next 数组值。这个值是几，模式串的指针就跳到第几个字符的位置（索引为几的位置），而主串指针保持不动！

图解地狱级难点：next数组的 while 回退逻辑

KMP算法中，最让新手抓狂的就是构建 next 数组时的这三行代码：

while (j > 0 && pattern[i] != pattern[j]) {
j = next[j – 1];
}

“为什么是 j = next[j-1]？怎么不是 j-1？这到底是在干嘛？” 别急，我们用一张图解把它扒得干干净净！

假设我们的模式串是 pattern = "ABACA"，我们正在计算它的 next 数组。

前情提要：

• i 代表当前正在处理的字符后缀末尾。

• j 代表当前已经匹配上的最长公共前缀的长度（同时也指向前缀的下一个字符）。

场景还原：当 i = 3 时发生了什么？

前面几步我们已经算出了 next 数组的前三个值：next[0]=0, next[1]=0, next[2]=1。 此时，指针 i 走到了索引 3，指针 j 在索引 1。

索引: 0 1 2 3 4
模式串: A B A C A
^ ^
j=1 i=3

第一步：对比模式串 pattern[i] 和 模式串pattern[j] 我们发现 pattern[3] 是 'C'，而 pattern[1] 是 'B'。 'C' != 'B'，匹配失败！

这说明什么？说明包含 'C' 的子串 "ABAC"，它的最长公共前后缀无法在上一段的基础上继续增加了。

第二步：触发 while 循环，执行 j = next[j – 1] 既然没法增加，那我们是不是要把 j 直接清零，从头开始算？ 千万不要！这也是KMP最聪明的地方。

我们虽然没法匹配这么长的，但我们可以“退而求其次”，找找看有没有更短一点的公共前后缀。

怎么找？去找出错位置 j 的前一个字符的 next 值。也就是 next[j – 1]。 此时 j = 1，所以我们去看 next[0]。 查表得知 next[0] = 0。

所以，j 被更新为 0。

第三步：回退后的重新比较 指针 j 回退到了索引 0 的位置，而 i 依然在索引 3 死死盯住 'C'。

索引: 0 1 2 3 4
模式串: A B A C A
^ ^
j=0 i=3

我们再次对比 pattern[3] 和 pattern[0]： 'C' 依然不等于 'A'！ 此时 j 已经是 0 了，退无可退（while 循环条件 j > 0 被打破）。

结局： 既然退无可退，说明完全没有公共前后缀。所以记录下 next[3] = 0。然后 i 继续安心往下走。

核心总结：什么是 j = next[j-1]？

用一句大白话来说：

j = next[j-1] 的本质就是：在这个较长的后缀中匹配失败了，我就去“前缀的前缀”里面找找，看看有没有更短的能匹配上！

这就好比俄罗斯套娃，最外层装不进去了，我们就打开看下一层能不能装进去，直到退到最核心（j=0）为止。

四、 核心代码实现 (C++版)

理解了原理，代码其实就是顺理成章的事情。这里给出带有详细注释的代码，大家可以结合注释再过一遍逻辑：

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 步骤 1：构建 next 数组 (前缀表)
vector<int> getNext(string pattern) {
int m = pattern.length();
vector<int> next(m, 0); // 初始化 next 数组全为 0

int j = 0; // j 表示最长公共前后缀的长度，也表示当前要匹配的前缀的末尾
for (int i = 1; i < m; i++) { // i 从 1 开始，表示当前子串的末尾
// 如果前后缀不相同，j 需要回退，回退到 next[j-1] 的位置
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j – 1];
}
// 如果前后缀相同，j 往前走一步
if (pattern[i] == pattern[j]) {
j++;
}
// 记录当前位置的 next 值
next[i] = j;
}
return next;
}

// 步骤 2：KMP 匹配过程
int kmpSearch(string text, string pattern) {
int n = text.length();
int m = pattern.length();
if (m == 0) return 0;

vector<int> next = getNext(pattern); // 获取 next 数组

int j = 0; // j 负责扫描 pattern
for (int i = 0; i < n; i++) { // i 负责扫描 text，永远不回退！
// 如果匹配失败，j 根据 next 数组进行回退
while (j > 0 && text[i] != pattern[j]) {
j = next[j – 1];
}
// 如果字符匹配成功，j 往下走
if (text[i] == pattern[j]) {
j++;
}
// 如果 j 走到了 pattern 的末尾，说明找到了完整的模式串
if (j == m) {
return i – m + 1; // 返回匹配成功的起始索引
}
}
return -1; // 没找到返回 -1
}

int main() {
string text = "ABABCABAA";
string pattern = "ABACA";
int index = kmpSearch(text, pattern);

if (index != -1) {
cout << "匹配成功！起始索引为: " << index << endl;
} else {
cout << "匹配失败！" << endl;
}
return 0;
}

五、 总结

KMP算法的难点其实全在 next 数组的推导和回退逻辑 上。只要你弄懂了“最长公共前后缀”的概念，知道主串指针 i 不回头、模式串指针 j 根据 next 数组找捷径，KMP 就不再是难啃的骨头了！

作为新手小白，这也是我学习KMP的一点心得。如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、评论区交流！