企业官网建设流程全解析

1. 项目概述：从一道408真题说起

最近在带学生复习数据结构，特别是备战计算机专业基础综合考试（也就是大家常说的408）的同学，几乎每个人都会在KMP算法这一块卡壳。而卡壳的核心，往往不是算法思想本身，而是那个让人又爱又恨的Next数组，以及它的进阶版Nextval数组。尤其是看到类似“求模式串ababaaababaa的Next数组和Nextval数组”这样的题目时，很多人的第一反应是头皮发麻，只能硬背公式，结果下次题目稍微一变，又不会了。

这其实非常可惜。KMP算法作为字符串匹配领域的里程碑，其核心思想——利用已匹配的信息避免主串指针回溯——是非常精妙的。而Next数组正是这一思想的“预计算”产物，它决定了当匹配失败时，模式串应该向右滑动多远。Nextval则是对Next数组的优化，进一步减少了不必要的比较。弄懂它们的求法，不仅是为了应付考试里那十来分，更是为了真正理解这种“空间换时间”的经典设计模式，这种思想在动态规划、状态机等众多领域都有体现。

我自己当年考研和后来在项目中做文本搜索引擎、日志分析工具时，都深刻体会到KMP及其变种算法的实用性。今天，我就以一个老程序员和过来人的身份，把Next和Nextval数组的求取问题掰开了、揉碎了讲清楚。我们不搞花架子，就用手算的方式，一步步推导，让你看到每一个数字是怎么来的，背后的逻辑是什么。目标是：看完这篇文章，你能独立、正确、快速地求解任何模式串的这两个数组，并且真正理解为什么这么做。

2. 核心概念与前置知识梳理

在动手计算之前，我们必须统一“语言”和“规则”。市面上关于Next数组的定义有细微差别，这直接导致了计算结果的不同。为了和408考研的主流教材（如王道、天勤）以及真题标准答案对齐，我们采用以下定义，这也是最容易理解、最不易出错的一种。

模式串（Pattern String）：我们要在主串中寻找的那个字符串。记为P = P[1]P[2]...P[m]。注意，这里我们从下标1开始计数，这是为了和Next数组的下标对齐，避免混淆。P[0]通常不使用或用作其他用途。

前缀（Prefix）与后缀（Suffix）：这是理解Next数组的基石。对于一个字符串"ababa"：

• 其前缀有："a","ab","aba","abab"（注意，不包括自身"ababa"）。
• 其后缀有："a","ba","aba","baba"（同样，不包括自身"ababa"）。

最长公共前后缀（Longest Proper Prefix which is also Suffix）：顾名思义，找一个字符串的所有前缀和后缀中，最长的那个相等的部分。对于"ababa"，其前缀集合和后缀集合的交集中，最长的是"aba"，长度为3。

Next[j]数组的定义：当模式串中第j个字符P[j]与主串对应字符失配时，模式串指针j应该回溯到的新位置。其值为：P[1]...P[j-1]这个子串的最长公共前后缀的长度 + 1。

• 特殊规定：Next[1] = 0。这表示如果第一个字符就失配，那么模式串整体右移一位，主串指针前进一位，从模式串头重新开始匹配（j回溯到0，但代码中会+1，等效于从1开始）。
• 另一种等价的感性理解：Next[j]是模式串在j位置“失败”后，其前缀可以“对齐”到的新位置，这个位置之前的部分已经和主串匹配过了，无需再比较。

Nextval[j]数组的定义：在Next[j]的基础上进行的优化。如果回溯后的新位置P[Next[j]]的字符与当前失配字符P[j]相同，那么这次回溯后的比较也注定会失败。因此，我们可以“递归地”向前寻找，直到找到一个字符不同的位置，或者到0。Nextval[j]就是优化后的回溯位置。

重要提示：有些资料（如严蔚敏版教材）的Next数组定义是“最长公共前后缀的长度”，其值比我们这里的定义少1。在解题时，务必先明确题目采用的是哪种定义。408考试通常采用我们本文所述的“回溯位置”定义。看清题目要求，是避免低级错误的第一步。

3. Next数组的手工求法详解与实战

理论说再多，不如动手算一遍。我们以模式串P = "ababaaababaa"为例，这是408真题和众多习题中的常客。我们一步一步推导它的Next数组。

我们的目标是求出一个数组Next[1..12]（串长m=12）。记住核心：Next[j]等于P[1..j-1]子串的最长公共前后缀长度 + 1。

步骤1：初始化

• Next[1] = 0。这是规定，表示第一个字符失配，模式串右移，从0开始（代码中会+1）。

步骤2：求Next[2]

• 子串是P[1..1] = "a"。
• 该子串的前缀集合：空集（因为不包括自身，长度为1的子串没有真前缀）。
• 该子串的后缀集合：空集。
• 最长公共前后缀长度 = 0。
• 因此，Next[2] = 0 + 1 = 1。
• 理解：当第二个字符b失配时，看前面一个字符a。“a”的前后缀最大匹配长度为0，所以回溯到位置0+1=1，即从模式串的第一个字符a开始重新与主串当前字符比较。

步骤3：求Next[3]

• 子串是P[1..2] = "ab"。
• 前缀："a"。
• 后缀："b"。
• 公共部分：无。最长公共前后缀长度 = 0。
• 因此，Next[3] = 0 + 1 = 1。

步骤4：求Next[4]

• 子串是P[1..3] = "aba"。
• 前缀："a","ab"。
• 后缀："a","ba"。
• 公共部分："a"。最长公共前后缀长度 = 1（“a”的长度）。
• 因此，Next[4] = 1 + 1 = 2。
• 理解：当第四个字符b失配时，看前面三个字符aba。“aba”有公共前后缀“a”，长度为1。这意味着模式串的前1位“a”和后1位“a”是相同的。所以，我们可以把模式串的前缀“a”滑动到刚才后缀“a”的位置，即从模式串的第2个字符开始比较。

步骤5：求Next[5]

• 子串是P[1..4] = "abab"。
• 前缀："a","ab","aba"。
• 后缀："b","ab","bab"。
• 公共部分："ab"。最长公共前后缀长度 = 2。
• 因此，Next[5] = 2 + 1 = 3。

步骤6：求Next[6]

• 子串是P[1..5] = "ababa"。
• 前缀："a","ab","aba","abab"。
• 后缀："a","ba","aba","baba"。
• 公共部分："aba"（长度3）。注意，“a”也存在，但不是最长的。
• 最长公共前后缀长度 = 3。
• 因此，Next[6] = 3 + 1 = 4。

步骤7：求Next[7]

• 子串是P[1..6] = "ababaa"。
• 前缀："a","ab","aba","abab","ababa"。
• 后缀："a","aa","baa","abaa","babaa"。
• 公共部分：只有"a"。最长公共前后缀长度 = 1。
• 因此，Next[7] = 1 + 1 = 2。

步骤8：求Next[8]

• 子串是P[1..7] = "ababaaa"。
• 前缀："a","ab","aba","abab","ababa","ababaa"。
• 后缀："a","aa","aaa","baaa","abaaa","babaaa"。
• 公共部分："a"。最长公共前后缀长度 = 1。
• 因此，Next[8] = 1 + 1 = 2。

步骤9：求Next[9]

• 子串是P[1..8] = "ababaaab"。
• 前缀："a","ab","aba","abab","ababa","ababaa","ababaaa"。
• 后缀："b","ab","aab","aaab","baaab","abaaab","babaaab"。
• 公共部分："ab"。最长公共前后缀长度 = 2。
• 因此，Next[9] = 2 + 1 = 3。

步骤10：求Next[10]

• 子串是P[1..9] = "ababaaaba"。
• 前缀："a","ab","aba","abab","ababa","ababaa","ababaaa","ababaaab"。
• 后缀："a","ba","aba","aaba","aaaba","baaaba","abaaaba","babaaaba"。
• 公共部分："aba"。最长公共前后缀长度 = 3。
• 因此，Next[10] = 3 + 1 = 4。

步骤11：求Next[11]

• 子串是P[1..10] = "ababaaabab"。
• 前缀："a","ab","aba","abab","ababa","ababaa","ababaaa","ababaaab","ababaaaba"。
• 后缀："b","ab","bab","abab","aabab","aaabab","baaabab","abaaabab","babaaabab"。
• 公共部分："abab"。最长公共前后缀长度 = 4。
• 因此，Next[11] = 4 + 1 = 5。

步骤12：求Next[12]

• 子串是P[1..11] = "ababaaababa"。
• 前缀："a","ab","aba","abab","ababa","ababaa","ababaaa","ababaaab","ababaaaba","ababaaabab"。
• 后缀："a","ba","aba","baba","ababa","aababa","aaababa","baaababa","abaaababa","babaaababa"。
• 公共部分："ababa"。最长公共前后缀长度 = 5。
• 因此，Next[12] = 5 + 1 = 6。

至此，我们得到完整的Next数组：

实操心得：手工计算时，最容易出错的地方在于找最长公共前后缀。一个技巧是，从可能的最长长度（子串长度-1）开始尝试，依次递减。例如对于“abab”，先看长度3的前缀“aba”和后缀“bab”是否相等？不等。再看长度2的前缀“ab”和后缀“ab”是否相等？相等，那么长度就是2。这个方法比枚举所有前后缀更高效。

4. Nextval数组的优化原理与递推求法

有了Next数组，Nextval数组的求解就有了基础。Nextval优化的动机非常直接：避免明知会失败的比较。

考虑这个场景：模式串P = "aaaaab"，假设我们已经算出其Next数组（部分）：当j=5（字符a）失配时，Next[5]=4，即回溯到j=4（字符a）进行比较。但P[5]和P[4]都是‘a’。既然在j=5时和主串的‘x’（非a）比较失败了，那么回溯到j=4与同一个主串字符‘x’比较，因为P[4] = ‘a’，所以这次比较也必然失败。这次回溯和比较就是无效的。

Nextval的思想就是：如果P[j] == P[Next[j]]，那么Nextval[j]应该等于Nextval[Next[j]]。这是一个递归或递推的过程，直到找到某个位置k，使得P[j] != P[k]，或者k=0。

Nextval数组的递推求法规则：

1. Nextval[1] = 0。第一个字符失配，没有优化空间，只能从头再来。
2. 对于j > 1：
   • 如果P[j] != P[Next[j]]，则Nextval[j] = Next[j]。因为回溯后的字符不同，这次回溯是“安全”的，可能成功。
   • 如果P[j] == P[Next[j]]，则Nextval[j] = Nextval[Next[j]]。因为回溯后字符相同，必然失败，所以直接采用更早位置（Next[j]位置）优化后的回溯值。

我们用刚才求得的P = "ababaaababaa"和它的Next数组来求Nextval。

步骤1：初始化

• Nextval[1] = 0。

步骤2：求Nextval[2]

• j=2,P[2]=‘b’,Next[2]=1,P[1]=‘a’。
• 判断：P[2] (‘b’) != P[Next[2]] (P[1]=‘a’)。
• 因此，Nextval[2] = Next[2] = 1。

步骤3：求Nextval[3]

• j=3,P[3]=‘a’,Next[3]=1,P[1]=‘a’。
• 判断：P[3] (‘a’) == P[Next[3]] (P[1]=‘a’)。
• 因此，Nextval[3] = Nextval[Next[3]] = Nextval[1] = 0。

步骤4：求Nextval[4]

• j=4,P[4]=‘b’,Next[4]=2,P[2]=‘b’。
• 判断：P[4] (‘b’) == P[Next[4]] (P[2]=‘b’)。
• 因此，Nextval[4] = Nextval[Next[4]] = Nextval[2] = 1。

步骤5：求Nextval[5]

• j=5,P[5]=‘a’,Next[5]=3,P[3]=‘a’。
• 判断：P[5] (‘a’) == P[Next[5]] (P[3]=‘a’)。
• 因此，Nextval[5] = Nextval[Next[5]] = Nextval[3] = 0。

步骤6：求Nextval[6]

• j=6,P[6]=‘a’,Next[6]=4,P[4]=‘b’。
• 判断：P[6] (‘a’) != P[Next[6]] (P[4]=‘b’)。
• 因此，Nextval[6] = Next[6] = 4。

步骤7：求Nextval[7]

• j=7,P[7]=‘a’,Next[7]=2,P[2]=‘b’。
• 判断：P[7] (‘a’) != P[Next[7]] (P[2]=‘b’)。
• 因此，Nextval[7] = Next[7] = 2。

步骤8：求Nextval[8]

• j=8,P[8]=‘b’,Next[8]=2,P[2]=‘b’。
• 判断：P[8] (‘b’) == P[Next[8]] (P[2]=‘b’)。
• 因此，Nextval[8] = Nextval[Next[8]] = Nextval[2] = 1。

步骤9：求Nextval[9]

• j=9,P[9]=‘a’,Next[9]=3,P[3]=‘a’。
• 判断：P[9] (‘a’) == P[Next[9]] (P[3]=‘a’)。
• 因此，Nextval[9] = Nextval[Next[9]] = Nextval[3] = 0。

步骤10：求Nextval[10]

• j=10,P[10]=‘b’,Next[10]=4,P[4]=‘b’。
• 判断：P[10] (‘b’) == P[Next[10]] (P[4]=‘b’)。
• 因此，Nextval[10] = Nextval[Next[10]] = Nextval[4] = 1。

步骤11：求Nextval[11]

• j=11,P[11]=‘a’,Next[11]=5,P[5]=‘a’。
• 判断：P[11] (‘a’) == P[Next[11]] (P[5]=‘a’)。
• 因此，Nextval[11] = Nextval[Next[11]] = Nextval[5] = 0。

步骤12：求Nextval[12]

• j=12,P[12]=‘a’,Next[12]=6,P[6]=‘a’。
• 判断：P[12] (‘a’) == P[Next[12]] (P[6]=‘a’)。
• 因此，Nextval[12] = Nextval[Next[12]] = Nextval[6] = 4。

最终，我们得到完整的Nextval数组：

对比Next和Nextval，可以发现很多位置的值被优化得更小了（如3->0， 2->1， 5->0， 6->4）。这意味着在KMP匹配过程中，发生失配时，模式串指针j可以回溯得更远，跳过更多必然失败的比较，从而提升效率。

注意事项：计算Nextval时，必须按顺序从j=1到j=m递推，因为Nextval[j]可能依赖于Nextval[Next[j]]，而Next[j]是小于j的。所以只要按顺序算，依赖的值总是已经计算好的。

5. 代码实现与算法逻辑验证

理解了手工计算过程，我们来看看代码如何实现。这不仅能验证我们手算的正确性，更是为了理解KMP算法是如何利用这两个数组的。这里给出C语言的实现，清晰且贴近考试要求。

#include <stdio.h> #include <string.h> // 生成Next数组 void getNext(char pattern[], int next[], int len) { int i = 1, j = 0; // i是模式串指针，j是前后缀长度指针/回溯位置 next[1] = 0; // 初始化 while (i < len) { if (j == 0 || pattern[i] == pattern[j]) { // 如果j为0（意味着从头开始匹配）或者当前字符相等 ++i; ++j; next[i] = j; // 记录Next值 } else { // 失配，j回溯 j = next[j]; } } } // 生成Nextval数组 (基于Next数组优化) void getNextval(char pattern[], int next[], int nextval[], int len) { nextval[1] = 0; // 初始化 for (int j = 2; j <= len; j++) { if (pattern[j] == pattern[next[j]]) { // 如果回溯后的字符与当前字符相同，则进一步优化 nextval[j] = nextval[next[j]]; } else { // 否则，优化后的位置就是Next数组的位置 nextval[j] = next[j]; } } } // 打印数组，方便调试 void printArray(char* name, int arr[], int len) { printf("%s: [", name); for (int i = 1; i <= len; i++) { printf("%d", arr[i]); if (i < len) printf(", "); } printf("]\n"); } int main() { // 模式串，我们使用下标从1开始，所以数组0位置空出或放串长度 char P[] = " ababaaababaa"; // 前面加一个空格，使得P[1]='a' int m = strlen(P) - 1; // 减去开头的空格 int next[m+1]; // 多分配一个，方便从1开始索引 int nextval[m+1]; getNext(P, next, m); getNextval(P, next, nextval, m); printf("模式串: %s\n", P+1); // 从P[1]开始打印 printArray("Next", next, m); printArray("Nextval", nextval, m); // 验证：手工计算的结果 int expected_next[] = {0, 0, 1, 1, 2, 3, 4, 2, 2, 3, 4, 5, 6}; // 下标0无用 int expected_nextval[] = {0, 0, 1, 0, 1, 0, 4, 2, 1, 0, 1, 0, 4}; printf("\n验证结果:\n"); int correct = 1; for (int i = 1; i <= m; i++) { if (next[i] != expected_next[i]) { printf("Next[%d] 错误: 计算值=%d, 期望值=%d\n", i, next[i], expected_next[i]); correct = 0; } if (nextval[i] != expected_nextval[i]) { printf("Nextval[%d] 错误: 计算值=%d, 期望值=%d\n", i, nextval[i], expected_nextval[i]); correct = 0; } } if (correct) { printf("恭喜，计算结果与手工推导完全一致！\n"); } return 0; }

这段代码的关键在于getNext函数中的while循环。它巧妙地用两个指针i和j在模式串上移动，i指向当前正在计算Next值的位置的后一个字符（可以理解为后缀的末尾），j指向前缀的末尾（同时也是Next[i]的候选值）。当P[i] == P[j]时，最长公共前后缀长度可以增加；失配时，j就利用已经计算好的Next[j]进行回溯。这个算法的时间复杂度是 O(m)，非常高效。

运行这段代码，输出结果会与我们手工计算的结果完全一致，这证明了我们推导过程的正确性。

实操心得：在代码实现时，下标处理是新手最容易出错的地方。务必统一约定：是让数组下标从0开始还是从1开始？我们的示例选择了从1开始，这样Next数组的下标和字符位置直观对应。如果你习惯从0开始，那么Next[0]=-1也是一种常见写法，其含义是“第一个字符失配时，模式串右移一位且主串指针后移”。无论哪种，原理相通，但推导出的数值会差1。在考试答题时，一定要明确写出你的下标起始约定。

6. 常见错误、疑难辨析与速查表

即使理解了原理，在实际做题和编码中，依然会碰到一些典型的“坑”。这里我总结了几类最常见的问题和疑惑点。

1. 下标起始问题导致的数值差异这是最大的混乱来源。主要有两种流派：

• 王道/天勤/408主流派（本文采用）：字符从P[1]开始存储，Next[1]=0。Next[j]表示失配时j应跳转到的位置。
• 严蔚敏教材/部分代码实现派：字符从P[0]开始存储，Next[0]=-1。此时Next[j]的值在数值上等于“最长公共前后缀长度”，而不是跳转位置。跳转位置需要做j = Next[j]操作。应对策略：拿到题目，首先看它给出的示例或定义。如果题目说“当匹配失败时，模式串向右滑动至…”，通常采用跳转位置定义（本文）。如果直接给出一个Next数组值，可以尝试用简单字符串（如“abab”）验证一下属于哪种。

2. 求最长公共前后缀时，漏掉“真”前缀/后缀公共前后缀必须是真前缀和真后缀，即不能是字符串本身。例如求“a”的公共前后缀时，前缀集合和后缀集合都是空集，长度为0，而不是1。这是定义问题，必须严格遵守。

3. Nextval计算中的递归优化理解不透Nextval的优化是递归的。当P[j] == P[Next[j]]时，Nextval[j]不是简单等于Next[j]-1之类的，而是等于Nextval[Next[j]]。这意味着可能连续优化多次。例如，在P=“aaaaa”中，Next[5]=4, 因为P[5]==P[4], 所以Nextval[5]=Nextval[4]；而Next[4]=3, 且P[4]==P[3], 所以Nextval[4]=Nextval[3]……最终Nextval[5]=Nextval[1]=0。这个过程在手工计算时要一步步递推，不能跳步。

4. 手工计算速度慢，容易乱对于长字符串，枚举所有前后缀确实繁琐。可以采用“递推法”口算Next数组，这更接近代码逻辑：

• Next[1]=0，假设已知Next[j]=k。
• 求Next[j+1]：
  • 若P[j] == P[k]，则Next[j+1] = k+1。
  • 若P[j] != P[k]，则令k = Next[k]，继续比较，直到k=0或相等。

用这个方法重新计算“ababaaababaa”的Next数组，会快很多，且不易错。Nextval则在Next的基础上按规则优化即可。

为了帮助大家快速自查，我整理了以下速查表：

7. 在KMP算法中的应用与性能对比

最后，我们来看看Next和Nextval数组是如何被KMP算法使用的，并直观感受一下Nextval带来的优化效果。

KMP匹配算法核心伪代码（使用Next数组）：

int KMP(char text[], char pattern[], int next[]) { int i = 1, j = 1; // i为主串指针，j为模式串指针 int n = strlen(text)-1, m = strlen(pattern)-1; // 假设下标从1开始 while (i <= n && j <= m) { if (j == 0 || text[i] == pattern[j]) { // 匹配成功，或j==0（即模式串第一个字符就失配，需要整体右移） ++i; ++j; } else { // 失配，模式串指针j回溯 j = next[j]; } } if (j > m) { return i - m; // 匹配成功，返回起始位置 } else { return 0; // 匹配失败 } }

将上述代码中的next数组替换为nextval数组，就是优化后的KMP算法。

性能对比实例： 假设主串T = "aaabaaaab"，模式串P = "aaaab"。

• 先计算Next数组:[0, 1, 2, 3, 4](下标1-5)。
• 再计算Nextval数组:[0, 0, 0, 0, 4]。

现在模拟匹配过程：

• 使用Next数组：

  1. T[1]=a匹配P[1]=a。
  2. T[2]=a匹配P[2]=a。
  3. T[3]=a匹配P[3]=a。
  4. T[4]=b失配P[4]=a。j=4回溯到Next[4]=3。
  5. T[4]=b比较P[3]=a，失配。j=3回溯到Next[3]=2。
  6. T[4]=b比较P[2]=a，失配。j=2回溯到Next[2]=1。
  7. T[4]=b比较P[1]=a，失配。j=1回溯到Next[1]=0，触发j==0条件，i++, j++。
  8. T[5]=a匹配P[1]=a... (后续省略) 可以看到，在T[4]这个位置，因为Next数组的“阶梯式”回溯，进行了多次（第4、5、6、7步）必然失败的比较（因为回溯后的字符都是a，而主串是b）。

• 使用Nextval数组：

  1. T[1]=a匹配P[1]=a。
  2. T[2]=a匹配P[2]=a。
  3. T[3]=a匹配P[3]=a。
  4. T[4]=b失配P[4]=a。j=4回溯到Nextval[4]=0，触发j==0条件，i++, j++。
  5. T[5]=a匹配P[1]=a... (后续省略) 优化后，在T[4]失配时，直接一步回溯到0，跳过了所有中间必然失败的步骤，效率显著提升。

对于模式串中有很多连续重复字符的情况，Nextval的优化效果极其明显。在实际的文本编辑器、IDE的查找功能，或者grep这类命令行工具中，使用的往往是优化后的KMP或其变种。

理解并掌握Next和Nextval数组，你就掌握了KMP算法的灵魂。下次再遇到408真题或者面试官问起字符串匹配，你完全可以自信地从原理讲到实现，从基础Next讲到优化Nextval，把这十分稳稳地拿到手。