【C++学习】KMP 算法优化：从 next 数组到 nextval，让匹配效率再升级
文章目录
- 前言
- 一、先回顾：标准 next 数组的 “小缺陷”
- 1. next 数组的核心作用
- 2. 标准 next 的冗余问题
- 二、nextval 的核心优化思想
- 1. nextval 的核心规则
- 2. 为什么是比较pattern[i+1] == pattern[next[i]]，而不是pattern[i] == pattern[next[i]]？
- 3. 举个具体例子：ABABA
- 4. C++代码实现
- 5. nextval 到底能省多少？什么时候最明显？
- 总结
前言
在字符串匹配的经典算法中，KMP 算法凭借其 O (n+m) 的时间复杂度（n 为主串长度，m 为模式串长度）成为首选方案，而next数组是 KMP 算法的核心 —— 它通过记录模式串的最长相等前后缀，避免了主串指针的回溯。但标准next数组存在冗余匹配的问题，nextval（优化版 next 数组）则能进一步精简匹配过程，让 KMP 算法效率更高。
本文将从「标准 next 数组的痛点」出发，详解 nextval 的核心思想，并结合实际代码（你提供的实现）拆解优化逻辑，帮你彻底理解这一 KMP 优化技巧。
一、先回顾：标准 next 数组的 “小缺陷”
1. next 数组的核心作用
next[i]表示模式串中pattern[0…i]的最长相等真前缀和真后缀的长度。
在 KMP 匹配过程中，当 pattern[j] 与 S[i] 不匹配时，利用已匹配的前缀信息，让 j 回退到当前位置的最长公共前后缀的后缀末尾下一位（j=next[j-1]），而非直接重置为 0，避免重复比较。
2. 标准 next 的冗余问题
比如模式串pattern = “aaaaa”，其 标准next 数组为：next = [0,1,2,3,4]。
使用标准的next数组与主串为"aaabaaaaa"匹配时，当匹配到主串第 4 位（字符b）与模式串第 4 位（字符a）不匹配时：
- 按标准 next，需要回溯到next[3]=3的位置（模式串第 3 位，字符a）；
- 但模式串第 3 位还是a，和第 4 位的a完全相同，匹配必然失败，这次回溯是无效的；
- 后续模式串的第 2 位，第 1 位也都还是a，和第 4 位的a完全相同，匹配都必然失败，这些回溯都是无效的；
- 理想情况下，应该直接回溯到更前面的有效位置（比如nextval[4]=0），跳过所有无效的重复匹配。
这就是标准 next 数组的核心问题：当模式串当前位置的字符与回溯位置的字符相同时，会产生无意义的回溯。而nextval的本质就是：在 next 数组的基础上，提前规避这种冗余。
二、nextval 的核心优化思想
1. nextval 的核心规则
nextval 的优化可以用一句话概括：
- 当回退后将要比较的字符，和当前失配位置的字符相同，则直接沿着回退链再跳一次。
nextval 数组相对next的优化逻辑为：
- 先计算next数组。然后根据next数组计算nextval。
- 对于模式串的第 i 位，若 (i < (pattern.size() - 1) && pattern[i+1] == pattern[next[i]])，则nextval[i] = nextval[next[i-1]]；否则nextval[i] = next[i]。
通俗来说：如果当前位置的后一个字符和回溯位置的字符相同，就直接继承回溯位置的优化值（跳过无效匹配）；如果不同，就保留原 next 值。
2. 为什么是比较pattern[i+1] == pattern[next[i]]，而不是pattern[i] == pattern[next[i]]？
是因为nextval[i]的目的，是为了当主串在 i+1 位置与模式串失配时，告诉程序模式串应该跳到哪里。
核心逻辑拆解
在 KMP 匹配过程中，如果主串在位置 i+1 发生了失配：
- 标准 next： 我们会查看 next[i]（假设值为 j），然后尝试用 pattern[j] 去匹配主串的那个失配位。
- 潜在问题： 如果恰好 pattern[i+1] 和 pattern[j] 是同一个字符，那么既然 pattern[i+1] 已经匹配失败了，pattern[j] 也必然会匹配失败。
- nextval 的改进： 就应该是如果发现 pattern[i+1] == pattern[j]，我们就直接把 next[i] 的值更新为更早之前的回退位置（nextval[i] = nextval[j-1]），从而跳过这次注定失败的比较。
3. 举个具体例子：ABABA
假设我们计算到 i = 2 (子串 ABA)：
- 计算出标准 next[2] = 1（即 j = 1，对应前缀 A）。
- 检查下一步： pattern[i+1] 是 pattern[3] (字符 B)。而 pattern[j] 是 pattern[1] (也是字符 B)。
- 发现相等： pattern[3] == pattern[1]。
- 结论： 如果主串在索引 3 处不是 B，那么跳回索引 1 去比 B 肯定还是错的。
- 优化： 此时 nextval[2] 就不记录 1 了，而是直接继承 nextval[0] 的值。
4. C++代码实现
nextval 有两种实现方式：
- 第一就是先计算next数组，然后对next数组进行优化。
- 第二在计算next数组的时候直接进行优化。
// 计算next
std::vector<int> getNext(const std::string& pattern) {
int m = pattern.size();
if (m == 0) return {}; // 处理空字符串
std::vector<int> next(m, 0); // next数组初始化为0，next[0]固定为0
int j = 0; // 前缀指针，记录最长相等前后缀的长度
for (int i = 1; i < m; ++i) { // 后缀指针i从1开始遍历
// 情况2：pattern[i] != pattern[j]，回退j，直到j=0或匹配成功
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
// 情况1：P[i] == P[j]，j++，更新next[i]
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
// 根据next数组优化nextval
std::vector<int> getNextVal(const std::string& pattern) {
int m = pattern.size();
if (m == 0) return {}; // 处理空字符串
std::vector<int> nextval(m);
nextval[0] = 0;
std::vector<int> next = getNext(pattern);
for (int i = 1; i < pattern.size(); i++) {
int j = next[i]; // 此时 j 是 pattern[0...i] 的最长前后缀长度
// 预判：如果 i+1 位失配，回退到的位置是 j
// 如果这两个位置字符一样，就产生“无效回退”
if (i < m - 1 && pattern[i + 1] == pattern[j]) {
// 注意：当 j 为 0 时，说明回退到了起点，直接设为 0
nextval[i] = (j > 0) ? nextval[j - 1] : 0;
} else {
nextval[i] = j; // 保持原样
}
}
return nextval;
}
// 直接优化
std::vector<int> getNextValDirect(const std::string& pattern) {
int m = pattern.size();
if (m == 0) return {}; // 处理空字符串
std::vector<int> nextval(m);
int j = 0;
nextval[0] = 0;
for (int i = 1; i < m; i++) {
// --- 1. 标准 next 计算过程 (回退) ---
while (j > 0 && pattern[i] != pattern[j]) {
j = nextval[j - 1];
}
// --- 2. 匹配成功，指针后移 ---
if (pattern[i] == pattern[j]) {
j++;
}
// --- 3. 核心优化：预判式 nextval 修正 ---
// 逻辑：如果 pattern[i+1] 在失配后跳到 pattern[j] 发现字符还是一样，
// 则直接继承更早的 nextval 值，避免重复比较。 j就是next[i];
if (i < m - 1 && pattern[i + 1] == pattern[j]) {
// 注意：当 j 为 0 时，说明回退到了起点，直接设为 0
nextval[i] = (j > 0) ? nextval[j - 1] : 0;
} else {
nextval[i] = j; // 正常记录当前最长相等前后缀长度
}
}
return nextval;
}
// KMP匹配主函数：返回模式串p在主串s中首次出现的起始索引，失败返回-1
int kmpSearch(const std::string& s, const std::string& p) {
int n = s.size();
int m = p.size();
if (m == 0) return 0; // 模式串为空，默认匹配成功
std::vector<int> next = getNext(p);
// std::vector next = getNextVal(p); // 三种方法选一个
// std::vector next = getNextValDirect(p);
int j = 0; // 模式串指针
for (int i = 0; i < n; ++i) { // 主串指针i不回溯，一直前进
// 匹配失败，根据next数组回退j
while (j > 0 && s[i] != p[j]) {
j = next[j - 1];
}
// 匹配成功，模式串指针前进
if (s[i] == p[j]) {
j++;
}
// 模式串全部匹配成功，返回起始索引
if (j == m) {
return i - m + 1;
}
}
return -1; // 匹配失败
}
5. nextval 到底能省多少？什么时候最明显？
- 模式串重复字符/重复结构越多（例如 aaaaaa…、abababab…），nextval 的收益越明显
- 因为这类串最容易出现 pattern[i+1] == pattern[next[i]]，产生“必然失败的重复比较”
- nextval 会把这种比较提前消掉，减少常数项开销
时间复杂度仍然是：
- 预处理：O(m)
- 匹配：O(n + m)
但 nextval 让匹配阶段更“少比较”。
总结
nextval 是对 KMP 算法的一次微小但精妙的改进。它通过在预处理阶段多进行一次字符比较，换取了匹配阶段可能的大量跳步。在处理 DNA 序列、二进制流等字符集较小的字符串匹配时，这种优化的威力尤为显著。
