目录

前言

发现

总结

博客主页：张栩睿的博客主页

欢迎关注：点赞+收藏+留言

系列专栏：c语言学习

       家人们写博客真的很花时间的，你们的点赞和关注对我真的很重要，希望各位路过的朋友们能多多点赞并关注我，我会随时互关的，欢迎你们的私信提问，也期待你们的转发！

       希望大家关注我，你们将会看到更多精彩的内容！！！

前言

       学了一个下午的KMP算法，一直弄不明白为什么next数组的那个回溯：k=next[k]，喜欢钻牛角尖的我一直到处查啊查啊，但是当我仔细观察next数组，并多举了几个例子以后，才发现回溯的意义。

发现：

       通过大量的举例子发现，next数组，要么就是0 0 0 0，要么就是0 1 2 3...递增之后，直接跳回0或1，元素0后面的元素，会非递减，元素1后面的元素，不是0就是2，非0元素后面，要么是直接变为0或1，要么就递增。想到这里，我就发现如果在递增的时候发生不相同的情况，发生回溯，就会一直回溯到首元素，因为我们会惊奇的发现元素通过回溯，他的值没有发生改变！所以代码我们可以写成这样，就不用回溯了！因为回溯的本质就是找到首元素！

       从这里我们就可以看到这些规律

void GetNext(int* next, char* sub)
{
  next[0] = -1;
  if (strlen(sub) == 1)
    return;
  next[1] = 0;
  int k = 0;
  int i = 2;
  while (i < strlen(sub))
  {
    if (sub[i - 1] == sub[k])
    {
      next[i] = k + 1;
      i++;
      k++;
    }
    else if(sub[0]==sub[i-1])
    {
      sub[i]=1;
      i++;
      k++;
    }
    else if (sub[0] != sub[i - 1])
    {
      sub[i] = 0;
      i++;
      k++;
    }
  }
}

总结

       算法太难了！大家一定要好好学习呜呜呜辛苦各位小伙伴们动动小手，三连走一波 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！