🌹作者:云小逸

📝个人主页:云小逸的主页

📝码云：云小逸 (YunXiaoYi003) - Gitee.com

🤟motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。希望春天来之前，我们一起面朝大海，春暖花开！🤟

👏专栏：C语言初阶👏日常杂记👏

求字符串的next数组：

方法一：

这里我们将next数组第1,2位分别设为0，1（还有-1,0这种设法，这里先将其设为0,1若有需要再减一即可）

后面求解每一位的next值时，根据前一位进行比较。

从第三位开始，将前一位与其next值对应的内容进行比较，

如果相等，则该位的next值就是前一位的next值加上1；

如果不等，向前继续寻找next值对应的内容来与前一位进行比较，

直到找到某个位上内容的next值对应的内容与前一位相等为止，

则这个位对应的值加上1即为需求的next值；

如果找到第一位都没有找到与前一位相等的内容，那么求解的位上的next值为1。

总结：相等则加一，不等则向前寻找，找到加一，找不到为一。

方法二：

1.先求前缀后缀最长公共元素长度 。“前缀后缀最长公共元素长度”这个名词可能比较难懂，稍安勿躁，且听本公子(*^▽^*)娓娓道来：

编辑

（请多多关注，三连，图自己一笔一画画的φ(>ω<*) 创作不易）

编辑

2.将各个对应的前缀后缀最长公共元素长度 整体向后移一位，将第一位设为-1。就得到了其的next数组（第1，2位-1,0的情况）

完整代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void prefix_table(char pattern[], int prefix[], int n)//求出next数组
{
  prefix[0] = 0;
  int len = 0;
  int i = 1;
  while (i < n)
  {
    if (pattern[i] == pattern[len])
    {
      len++;
      prefix[i] = len;
      i++;
    }
    else
    {
      if (len > 0)
      {
        len = prefix[i];
      }
      else
      {
        prefix[i] = len;
        i++;
      }
    }
  }
}
void move_prefix_table(int prefix[], int n)//向后移动next数组
{
  int i;
  for (i = n - 1; i > 0; i--)
    prefix[i] = prefix[i-1];
  prefix[0] = -1;
}
int main(void)
{
  char pattern[] = "ABABCABAA";
  int n = 9;
  int prefix[9]={0};
  prefix_table(pattern, prefix, n);
  move_prefix_table(prefix, n);
  int i;
  for (i = 0; i < n; i++)
  {
    printf("%d   ", prefix[i]);
  }
  return 0;
}