KMP 算法中 next 数组的构建函数 get_next
KMP 算法中 next 数组的构建函数 get_next ，负责计算模式串的 next 数组，核心是通过递推找到每个位置的 “最长相等前缀后缀长度”。（下标从 1 开始）：
一、函数作用
get_next(SString T, int next[]) 的任务：
为模式串 T 生成 next 数组，next[i] 表示 模式串中第 i 个字符失配时，应该回退到的位置（本质是 “前 i-1 个字符的最长相等前缀后缀长度”）。
二、代码逐行解析
void get_next(SString T, int next[]) {// 初始化：// i：模式串当前处理到的位置（从 1 开始，对应字符 T.ch[1]）// j：记录当前最长相等前缀后缀的长度（初始为 0，对应“没有前缀”）i = 1; j = 0; // next[1] 固定为 0（模式串第一个字符失配时，没有前缀可回退，特殊处理）next[1] = 0; // 循环条件：i 遍历模式串的每个字符（直到模式串末尾）while (i < T.length) { // 情况 1：j=0（回到起点） 或 当前字符匹配（T.ch[i] == T.ch[j]）if (j == 0 || T.ch[i] == T.ch[j]) { // i、j 同时后移，扩展匹配长度++i; ++j; // 记录 next[i]：当前最长相等前缀后缀长度是 jnext[i] = j; } // 情况 2：当前字符不匹配（T.ch[i] != T.ch[j]）else { // j 回退到 next[j]（找更短的前缀后缀继续匹配）j = next[j]; }}
}
三、核心逻辑拆解（结合递推思想）
-
初始化：
i=1从模式串第二个字符开始（第一个字符next[1]=0已固定）。j=0表示 “当前没有匹配的前缀”。
-
循环处理每个字符：
-
匹配时（
T.ch[i] == T.ch[j]）：
i和j同时后移，next[i] = j表示 “前i个字符的最长相等前缀后缀长度是j”。
例：模式串ababc，当i=3（字符a）、j=1（字符a）匹配时，i++=4，j++=2，next[4]=2（前 4 个字符abab的最长相等前缀后缀是ab，长度 2）。 -
失配时（
T.ch[i] != T.ch[j]）：
j = next[j]让j回退到更短的前缀位置，继续尝试匹配。
例：模式串ababc，若i=5（字符c）、j=3（字符a）失配，j = next[3] = 1（回退到更短的前缀），再比较T.ch[5]和T.ch[1]。
-
四、对于i，j可能不见名知意，有点混乱，那下面将它们换掉 ，并再次进行解释
①、重命名变量后的代码（下标从 1 开始）
// 生成模式串 T 的 next 数组
// next[position] 表示：当模式串在 position 位置失配时，应回退到的位置
void get_next(SString T, int next[]) {// current_pos：当前处理到模式串的哪个位置（初始从第二个字符开始）int current_pos = 1;// prefix_len：当前最长相等前缀的长度（初始为 0，表示无前缀）int prefix_len = 0;// 第一个字符失配时，只能回退到模式串开头（下标 0，实际代码中用 0 表示）next[1] = 0;// 遍历模式串的每个字符（从第二个开始，直到末尾）while (current_pos < T.length) {// 情况 1：prefix_len 回退到 0（回到起点），或者当前字符匹配成功if (prefix_len == 0 || T.ch[current_pos] == T.ch[prefix_len]) {// 继续匹配下一个字符current_pos++;prefix_len++;// 记录：当匹配到 current_pos 位置失配时，应回退到 prefix_len 位置next[current_pos] = prefix_len;}// 情况 2：当前字符匹配失败else {// 回退 prefix_len 到更短的前缀位置，继续尝试匹配prefix_len = next[prefix_len];}}
}
②、关键变量解释
| 原变量 | 新变量 | 含义 |
|---|---|---|
i | current_pos | 当前处理到模式串的哪个位置（对应字符 T.ch[current_pos]） |
j | prefix_len | 当前最长相等前缀的长度，也表示前缀的下一个待匹配位置（T.ch[prefix_len]） |
next | next | 核心数组，next[pos] 表示模式串在 pos 位置失配时应回退到的位置 |
③、核心逻辑拆解（带例子）
以模式串 T = "ABABC"（下标从 1 开始）为例，逐步推导 next 数组：
1. 初始化
current_pos = 1; // 处理第 1 个字符 'A'
prefix_len = 0; // 无前缀
next[1] = 0; // 第一个字符失配时，回退到 0（实际逻辑中表示从头开始）
2. 处理 current_pos = 1（字符 A）
prefix_len = 0→ 进入if分支：current_pos++; // 2 prefix_len++; // 1 next[2] = 1; // 表示：当匹配到第 2 个字符失配时，应回退到第 1 个字符
3. 处理 current_pos = 2（字符 B）
T.ch[2] = 'B'，T.ch[1] = 'A'→ 不匹配 → 进入else分支：prefix_len = next[1] = 0; // 回退到 0- 再次循环：
prefix_len = 0→ 进入if分支：current_pos++; // 3 prefix_len++; // 1 next[3] = 1; // 表示：当匹配到第 3 个字符失配时，应回退到第 1 个字符
4. 处理 current_pos = 3（字符 A）
T.ch[3] = 'A'，T.ch[1] = 'A'→ 匹配 → 进入if分支：current_pos++; // 4 prefix_len++; // 2 next[4] = 2; // 表示：当匹配到第 4 个字符失配时，应回退到第 2 个字符
5. 处理 current_pos = 4（字符 B）
T.ch[4] = 'B'，T.ch[2] = 'B'→ 匹配 → 进入if分支：current_pos++; // 5 prefix_len++; // 3 next[5] = 3; // 表示：当匹配到第 5 个字符失配时，应回退到第 3 个字符
四、总结
get_next 函数的核心逻辑：
- 匹配成功：扩展当前前缀长度，并记录
next值。 - 匹配失败：回退到更短的前缀位置（通过
next数组），继续尝试匹配。