void getNext(char p[], int next[]) {
    int i = 0, j = -1;
    next[0] = -1;
    int len = strlen(p);
    while (i < len) {
        if (j == -1 || p[i] == p[j]) {
            i++;
            j++;
            next[i] = j; // 这是核心，在i++，j++后赋值
        } else {
            j = next[j];
        }
    }
}

KMP算法（字符串匹配）的next数组计算优化 KMP算法是一种高效的字符串匹配算法，其核心在于当匹配失败时，能够利用已匹配的信息，避免主串指针回退，从而将时间复杂度优化到O(n+m)。而算法的关键组成部分是一个被称为“next”的数组（或称为“部分匹配表”），它指导着当匹配失败时，模式串的指针应该回退到哪个位置。 1. 问题引入：暴力匹配的低效性 假设我们有一个主串 S 和一个模式串 P 。 暴力匹配的做法是，从 S 的每一个位置开始，尝试与 P 进行匹配。 一旦发现某个字符不匹配，就将 S 的指针回退到本次匹配起始位置的下一个字符， P 的指针重置为0，然后开始新一轮匹配。 这种方法的效率很低，在最坏情况下时间复杂度为 O(n* m)。 2. KMP算法的核心思想：利用已匹配的信息 KMP算法的高明之处在于，它认为当 S[i] 和 P[j] 不匹配时， S 的指针 i 不需要回退 。因为我们已经知道了 S[i-j : i-1] 这一段子串（即从 i 往前数 j 个字符）和 P[0 : j-1] 是完全匹配的。问题的关键变成了：在 P[0 : j-1] 这个子串中，寻找一个最长的、相等的 真前缀 和 真后缀 。 前缀： 指除了最后一个字符以外的所有头部子串的集合。 后缀： 指除了第一个字符以外的所有尾部子串的集合。 真前缀/真后缀： 强调不能是字符串本身。 例如，对于字符串 "ABABA"： 真前缀有："A", "AB", "ABA", "ABAB" 真后缀有："BABA", "ABA", "BA", "A" 其最长的相等真前缀和真后缀是 "ABA"，长度为3。 3. next数组的定义 next 数组是针对模式串 P 预先计算好的一个数组。 next[j] 的定义是：在子串 P[0..j] （即从P的开头到第j个字符）中，使得 真前缀 P[0..k-1] 等于 真后缀 P[j-k+1..j] 的最大 k 值。 简单来说， next[j] 的值就是 P[0..j] 这个子串的 最长相等真前缀和真后缀的长度 。 当 j=0 时，只有一个字符，没有真前缀/真后缀，我们规定 next[0] = -1 （或0，实现有差异，但逻辑等价，这里采用-1的约定）。 对于 j>0 ， next[j] 的值就是上述定义的长度。 示例： 模式串 P = "ABABAC" | j | P[ 0..j] | 所有真前缀 | 所有真后缀 | 最长相等前后缀 | next[ j ] | | :--- | :------ | :--------------------- | :--------------------- | :------------- | :------ | | 0 | "A" | [] | [ ] | 无 | -1 | | 1 | "AB" | [ "A"] | [ "B" ] | 无 (长度0) | 0 | | 2 | "ABA" | [ "A", "AB"] | [ "BA", "A" ] | "A" (长度1) | 1 | | 3 | "ABAB" | [ "A","AB","ABA"] | [ "BAB","AB","B" ] | "AB" (长度2) | 2 | | 4 | "ABABA" | [ "A","AB","ABA","ABAB"]| [ "BABA","ABA","BA","A" ]| "ABA" (长度3) | 3 | | 5 | "ABABAC"| ... | ... | 无 (长度0) | 0 | 所以， next 数组为 [-1, 0, 1, 2, 3, 0] 。 4. 如何使用next数组进行匹配？ 匹配过程如下，主串指针为 i ，模式串指针为 j ： 初始化 i = 0 , j = 0 。 循环，直到 i 到达 S 的末尾或 j 到达 P 的末尾。 如果 j == -1 （意味着没有任何匹配，从模式串头重新开始） 或者 S[i] == P[j] ，则 i 和 j 都加1，继续比较下一个字符。 否则（即 S[i] != P[j] 且 j != -1 ），匹配失败。此时，我们不回退 i ，而是将 j 设置为 next[j] 。这相当于将模式串向右“滑动”了 j - next[j] 位。 5. 如何计算next数组？（优化前的方法） 计算 next 数组本身也是一个字符串匹配问题，我们可以用类似KMP的方法来求解。假设我们已经知道了 next[0], next[1], ..., next[j] ，现在要求 next[j+1] 。 我们定义两个指针： i ：指向当前要计算 next 值的位置的前一个位置（即 i 从0开始，对应计算 next[1] ）。 j ：指向前缀的末尾（也可以理解为上一个已经计算好的最长相等前后缀的长度）。 算法步骤： 初始化： next[0] = -1 。令 i = 0 , j = -1 。 循环，当 i < len(P) - 1 时（因为我们要计算到 next[len(P)-1] ）： 如果 j == -1 或者 P[i] == P[j] ： i++ , j++ next[i] = j // 如果P[ i]等于P[ j]，那么next[ i ]自然就是j+1 否则： j = next[j] // 匹配失败，j回退 这个过程可以理解为：用模式串自身的前缀去匹配自身的后缀。 6. next数组计算的优化 上述方法计算出的 next 数组有时存在冗余。考虑一个例子： P = "ABAB" ，用上述方法计算 next 数组： next[0] = -1 i=0, j=-1 -> j=-1 -> i=1, j=0 -> next[1] = 0 i=1, j=0 -> 比较 P[1]('B') 和 P[0]('A') ，不相等 -> j = next[0] = -1 i=1, j=-1 -> j=-1 -> i=2, j=0 -> next[2] = 0 ? 等等，这里错了，根据定义，"ABA"的最长相等前后缀是"A"，长度1。 让我们重新严格按照定义和算法推导 P="ABAB" 的 next 数组： next[0] = -1 求 next[1] (i=0, j=-1): j=-1 -> i=1, j=0 -> next[1] = 0 求 next[2] (i=1, j=0): 比较 P[1]('B') 和 P[0]('A') ，不相等 -> j = next[0] = -1 (i=1, j=-1): j=-1 -> i=2, j=0 -> next[2] = 0 ? 但根据定义，"ABA"的最长相等前后缀是"A"，长度1。这里算法出错了。 修正与优化： 实际上，标准的、未优化的 next 数组计算算法是正确的。上面的推导错误在于我跳过了关键一步。让我们重新、更仔细地推导 P="ABAB" ： next[0] = -1 计算 next[1] (i=0, j=-1)： 因为 j == -1 , 所以执行 i++; j++; next[i] = j 。 i 变为 1, j 变为 0。 next[1] = 0 。 计算 next[2] (i=1, j=0)： 比较 P[1]('B') 和 P[0]('A') ，不相等。 j = next[0] = -1 。 现在 j == -1 ，所以执行 i++; j++; next[i] = j 。 i 变为 2, j 变为 0。 next[2] = 0 ？ 等等，还是不对！"ABA" 的最长相等前后缀明明是 "A"，长度为1。 问题根源与优化方案： 问题出在算法的实现细节上。一个更清晰且正确的未优化版本如下（以 P="ABAB" 为例）： next[0] = -1 i = 0, j = -1 while i < len(P) - 1: if j == -1 or P[i] == P[j]: i++ // i 现在指向我们 要计算 next值的位置 j++ next[i] = j // 此时， P[0..j-1] 是 P[0..i-1] 的一个相等前后缀，长度为 j 。 else: j = next[j] 让我们严格按此执行： 初始： i=0, j=-1, next[0]=-1 第1轮循环： j == -1 为真 -> i=1, j=0 -> next[1] = 0 第2轮循环： i=1, j=0 。比较 P[1]('B') 和 P[0]('A') ，不相等 -> j = next[0] = -1 第3轮循环： i=1, j=-1 。 j == -1 为真 -> i=2, j=0 -> next[2] = 0 ? 还是不对！ 真正的优化点（Nextval数组）： 这里揭示了一个关键点：我们通常课堂上讲的“优化”，其实是计算一个叫做 nextval 的数组，它是对 next 数组的进一步优化。而上面计算 next 数组的基础算法本身是正确的，但我的例子 P="ABAB" 的 next[2] 根据定义到底是多少？ 让我们回到定义，对 P="ABAB" ： j=2, P[0..2] = "ABA" 真前缀: "A", "AB" 真后缀: "BA", "A" 最长相等前后缀是 "A"，长度为1。所以 next[2] 应该是 1。 为什么算法算出来是0？因为算法是 递推 的，它找到的 j 是 P[i] 和 P[j] 比较时，如果相等就 j+1 作为 next[i] 。当 i=2 时，我们比较的是 P[2] 和 P[0] 吗？不，在算法中，当 i=1 时比较失败后， j 回退到 -1 ，然后 i 和 j 都增加， i 变成2， j 变成0，然后 next[2] 被赋值为0。这意味着算法认为 P[0..2] 的最长相等前后缀长度是0？这显然是错的。 结论：经典next数组计算算法 实际上，经典且正确的 next 数组计算算法如下（与KMP匹配过程高度一致）： 注意 while (i < len) 而不是 i < len - 1 。让我们用这个算法计算 P="ABAB" (len=4)： i=0, j=-1, next[0]=-1 循环开始 ( i=0 < 4 )： j == -1 -> True i++ -> i=1 j++ -> j=0 next[1] = 0 循环 ( i=1 < 4 )： 比较 p[1]('B') 和 p[0]('A') -> 不相等 j = next[0] = -1 循环 ( i=1 < 4 )： j == -1 -> True i++ -> i=2 j++ -> j=0 next[2] = 0 // 这里还是不对！ 看来问题依然存在。这表明要么是算法描述有细微差别，要么是对 next 数组的定义有不同理解。一种常见的定义是： next[j] 表示当 P[j] 匹配失败时， j 应该跳转到的位置。在这种定义下， next[0] = -1 ，而对于 j>0 ， next[j] 是 P[0..j-1] 的最长相等真前后缀的长度。 按照这个定义，对于 P="ABAB" ： next[0] = -1 (约定) next[1] : P[0..0] = "A" , 最长相等真前后缀长度0。 next[2] : P[0..1] = "AB" , 真前缀[ "A"]，真后缀[ "B" ]，无公共，长度0。 next[3] : P[0..2] = "ABA" , 真前缀[ "A","AB"]，真后缀[ "BA","A" ]，公共最长"A"，长度1。 所以 next = [-1, 0, 0, 1] 。 用这个定义再去看那个算法，就正确了！算法中的 next[i] = j 是在 i 和 j 自增 后 执行的，此时 i 指向的是当前计算的位置，而 j 的值正是 P[0..i-1] 的最长相等前后缀的长度。所以算法是正确的。我之前的错误在于混淆了“到j为止”和“到j-1为止”的子串。 优化计算（Nextval数组）： 现在讲真正的优化。基础 next 数组有时不够好。例如， P="AAAAA" ， next = [-1,0,1,2,3] 。如果在 j=3 时失配，根据 next[3]=2 ，会回退到 j=2 ，但 P[3] 和 P[2] 都是 'A'，这次比较必然还是失配（如果和主串比失配，那么和模式串自己的上一个相同字符比也会失配），然后要继续回退到 j=1 ，再回退到 j=0 。这产生了多次不必要的回退。 优化思路：在计算 next 数组时，如果发现回退后的字符 P[j] 和当前字符 P[i] (其实是回退前的字符) 是相同的，那么这次回退后的比较注定失败，我们可以直接使用更早的回退位置。即，在赋值 next[i] = j 之前，先检查 P[i] 是否等于 P[j] ： 如果相等，那么 nextval[i] = nextval[j] 。因为如果 P[i] 匹配失败，回退到 j 后由于 P[i] == P[j] ，必然再次失败，所以应该直接使用 j 的回退位置 nextval[j] 。 如果不相等，那么 nextval[i] = j 。 这个优化后的数组通常被称为 nextval 数组。它进一步减少了不必要的比较次数。 总结 KMP算法的 next 数组计算是其精髓所在。理解其递推求解的过程（自身匹配自身），并掌握其优化版本 nextval 的计算，是彻底掌握KMP算法的关键。这个过程体现了字符串匹配中“利用已知信息避免重复比较”的核心思想。