C语言KMP算法next[]数组的实现

现在Next[]数组的运行逻辑大概是明白了，但是如何以代码实现，我看了几篇文章还是没有理解，其中指针回退的代码是怎样实现的呢？

参考：https://blog.csdn.net/weixin_64182409/article/details/127160192

• 这篇博客: 串的模式匹配KMP算法C/C++代码实现中的 next数组： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 计算next值有两种方法：
  第一种是根据前一位的next值，逐个比较是否相等（后面代码用此种方法）

  第二种是求第n位时，比较前n-1位得出最长前后缀的匹配长度k，
  则第n位的next值位k+1。(适用于手算做题)

• 以下回答由chatgpt基于相关博客总结生成:

  我可以给出一个C语言实现KMP算法next[]数组的示例代码，核心思想就是在匹配的过程中，根据最大公共前后缀的长度来计算每个位置的next值，这样可以避免在匹配过程中做无用的回溯。具体实现示例代码如下：

  void get_next(char *pattern, int *next, int len) {
      int i = 0, j = -1;
      next[0] = -1;  // 初始化next[0]=-1
      while (i < len) {
          if (j == -1 || pattern[i] == pattern[j]) {
              i++;
              j++;
              next[i] = j;
          }
          else {
              j = next[j];
          }
      }
  }
  
  int main() {
      char mainString[] = "ababcabcababababc";
      char subString[] = "abcababab";
      int mainLen = strlen(mainString);
      int subLen = strlen(subString);
      int next[subLen + 1];
      get_next(subString, next, subLen);  // 计算next数组
      for (int i = 0; i <= subLen; i++) {
          printf("%d ", next[i]);  // 输出next数组，用于检查正确性
      }
      return 0;
  }
  

  该示例代码中，get_next函数用于计算next数组，其中数组next的长度要加1，因为在最后一个位置需要记录整个模式串的长度，而数组的下标是从0开始计数的。在while循环中，如果匹配成功，i和j指针都要加1，同时next[i]被赋值为j+1，因为下一个匹配可能是以j+1为开始的；如果匹配不成功，j指针回溯到next[j]，继续匹配。在执行完该函数之后，next数组中保存的就是每个位置的最大公共前后缀的长度。