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];  }}
}

三、核心逻辑拆解（结合递推思想）

1. 初始化：

   • i=1 从模式串第二个字符开始（第一个字符 next[1]=0 已固定）。
   • j=0 表示 “当前没有匹配的前缀”。

2. 循环处理每个字符：

   • 匹配时（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 函数的核心逻辑：

1. 匹配成功：扩展当前前缀长度，并记录 next 值。
2. 匹配失败：回退到更短的前缀位置（通过 next 数组），继续尝试匹配。