今天也是学习了KMP算法，由于next数组有三种模型，刚开始让我很是错乱，因为当时不知道，后来才发现原来next数组的版本有三种，让我纠结了好久，下面是next数组的三种模型。
刚开始我学的是第一种，那个是最大前缀，求next数组的时候应该不复杂，到时到kmp主函数的时候可能会变复杂，这一种我是在知乎上看到的，这位博主讲的很好，我直接理解了kmp的原理以及最大前缀的作用，链接如下：(4 封私信 / 56 条消息) 如何更好地理解和掌握 KMP 算法? - 知乎 (zhihu.com)
但是这位博主的编程语言用的是python，而我没有学过python，看着确实不舒服，于是乎我又在csdn上找了几篇文章，随后我看到了一篇好文章，这篇文章讲解的是第二种next数组，也是最常用的一个版本，讲的很好，我本来不愿舍弃刚理解的第一种，不过这种算法还是大众常用的比较好：(69条消息) KMP算法图文详解（为什么是next[0]=-1、next[j]=k和k=next[k]）_快乐江湖的博客-CSDN博客_kmp算法
这位博主写的代码确实让我收获了不少，对于kmp也是增进了很多理解，总算学会了，下面是我对代码的一些理解，原理大家就看上面的两篇文章吧
class Solution { public: int* kmp(string str) { int* next = new int[str.size()]; int k = -1;//这里k==-1，是为了和第十行和第15行相呼应，好进行回溯。 int j = 0; next[0] = -1;//next==-1也是与15行相呼应，能够进行回溯的处理。 while(j<str.size()-1){ if(k == -1||str[j] == str[k]){//这里是让j动起来如果相等的话就同时前进 j++; k++; next[j] = k;//对next数组进行赋值，注意我是第二种next数组 } else k = next[k];//这里是回溯 } return next; } int strStr(string haystack, string needle) { if(haystack.size()<needle.size()){ return -1; } int* next = new int [haystack.size()]; int i = 0; int j = 0; int sum = needle.size();//这里我建立了一个变量，因为.size()不能直接与负数比较 //这点我写题目的时候困扰了好久找不出问题，后来还是一直调试才发现j==-1时while函数就不进入循环了 next = kmp(needle); while(i<haystack.size()&&j<sum){ if(j==-1||haystack[i]==needle[j]){//这里跟next数组的建立有异曲同工之妙 //很类似，大家可以编写两个字符串来验证这个流程，在一步一步的迭代中你们就会慢慢懂得这一串代码 //为什么这样写了 i++; j++; } else j = next[j];//回溯 } if(j>=needle.size()){ return i-needle.size();//这里是返回下标 } else return -1;//未找到返回-1; } };
总的来说算法这种东西，你会了就真的觉得简单，不会就会觉得很难，但是只要你肯花时间，我相信再难也可以搞懂的。
