原题：

大一学的数据结构全忘了，做题看到的，整个人都懵了。。
网上看了很多的解析，好多博主抛出一个概念，然后没有解析，对我这种弱渣来说更加懵逼了~下面是我总结的一个简单的计算方法

首先介绍2个概念，字符串的前缀和后缀（这里的前缀是不包括最后一个字符的子串，后缀是不包含第一个字符的子串）。
拿题目中的字符串a=’‘babab’'举例，
首先第一位0，第二位1。这个是固定的。

第三位，字符串是“bab”，这时候“bab”的前缀有b，ba；后缀有ab，b，可以看出前后缀相等的最长的字符串只有b，因为b的长度是1，所以这里第三位的next值就是1。

第四位，字符串是“baba”，前缀是b,ba,bab；后缀是aba,ba,a。这里可以看出前后缀相等的最长的字符串是ba，长度是2，因此第四位的next值是2。

第五位，字符串是“babab”，前缀是b,ba,bab,baba；后缀是abab,bab,ab,b。这里可以看出前后缀相等的最长的字符串是bab，长度是3，因此第五位的next值是3。

本文章就专讲kmp，暴力匹配就不讲了（我相信能搜索kmp的，暴力匹配算法应该也都了解过了）
为什么网上那么多讲kmp 我还发文章，很多文章我觉得讲的不是太通俗易懂，大多数我看起来都觉得有些懵逼

KMP介绍

提示：以下信息来源百度

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)

上面讲了kmp需要求匹配字符串的next数组来快速匹配，那我们先来讲解一下如何求next数组

一、求Next数组

求Next数组前我们需要了解字符串的前缀表与后缀表

前后缀表

如字符串“ABCD”的前后缀表

了解完字符串前后缀，接下来我们要开始求最长公共前后缀

求最长公共前后缀

我们以“aabaac”为例

字符串中要没有公共的前后缀就为0

从以上方法就能求出字符串“aabaac”的最长公共前后缀数组为
[0,1,0,1,2,0]

最长相等前后缀表转Next数组

当然变成Next数组前还需要进行简单的处理（其实也就把最长公共前后缀数组右移而已）

在最长公共前后缀前面加上 -1 并去掉最后一位就是next数组了
Next数组的第一位永远是-1，第二位永远是0

注意：Next数组有很多种求法，依据匹配字符串的代码来做选择，我选择的方法next数组第一位是-1，还有另一种方法开头是0，但原理都是相同的所以不必纠结

二、使用Next数组来匹配字符串

为了能较好体现kmp算法：
主串：“aaacaacaaad”
模式串：“aaad”
模式串Next数组：[-1,0,1,2]

在主串和匹配串字符相同的情况下，指针 i 和 j 后移

或者遇到主串和匹配串字符不相同时 但next值为-1时指针 i 和 j 后移

步骤一：
1i、1j、2i、2j代表指针位置及步骤，中间字符相等的地方我就不讲了，就主要讲重点的地方

指针4i和4j的字符不相同，不匹配位置的next值为2（蓝色的a），所以需要将匹配串右移到匹配串索引2的位置

步骤二：
匹配串后移后指针i和j的字符依然还是不相同，不匹配位置的next值为1（蓝色的a），所以需要将匹配串右移到匹配串索引1的位置

步骤三：
匹配串后移后指针i和j的字符依然还是不相同，不匹配位置的next值为0（蓝色的a），所以需要将匹配串右移到匹配串索引0的位置

步骤四：
匹配串后移后指针i和j的字符依然还是不相同，但这时next值为-1，这就需要指针i和j向后移

步骤五：
指针i和j后移后，（中间字符相同的地方就不解说了），指针到3i和3j的字符不相同，next值为1，然后就和之前讲的步骤一样，需要将匹配串右移到匹配串索引1的位置

步骤六：
后面的步骤就不再多叙述，自己看图分析

步骤七：

步骤八：
然后这就匹配完成了

总结

代码后续会补充
非常感谢您能看到这，本人第一次写文章，所以我可能讲的不是很好，如有问题望大家能多多提醒，感谢。下次讲sunday算法
注：如看不懂，可以的话，麻烦您在评论区中发句看不懂，好让我知道我写的烂不烂

字符串next和nextval值的计算

针对字符串ababaabab，计算next和nextval的值。

• 第一行是序号，从0开始。

• 第二行是字符串的元素

• 第三行是next值，为当前位置前面字符串收尾重复的最长字符个数。

• 第四行是nextval值，当以next和以i为索引的字符不相同时，nextval值就是next值。当两个字符相同时，nextval值是以next为索引的nextval值。

next 值的计算

举个例子，当i=5时，计算方法如下：

其中，0和1的next值固定为-1和0.

nextval值的计算

0的nextval值固定为-1。

有时候下标从1开始，则nextval就是010104101.