KMP 算法优化：从 next 数组到 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<int> next = getNextVal(p);   // 三种方法选一个
    // std::vector<int> 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 序列、二进制流等字符集较小的字符串匹配时，这种优化的威力尤为显著。

KMP 算法优化：从 next 数组到 nextval，让匹配效率再升级