KMP算法（kmp） next数组算法解析

关于KMP算法，CSDN有很多优质的博文，结合各位大佬的总结，我按照自己的想法尽量解释KMP算法（全文没有推导公式，因为我也不会。）
先简单介绍一下KMP算法的内容：
相对于暴力算法，KMP算法的时间复杂度较小，只回溯模式串中i，（i对应模式串的位置，j对应主串的位置），KMP算法模式串不需要回溯到第一位，只需要利用前缀和后缀，这样子的话就可以一次性得挪动好几位，以此来缩小时间复杂度，核心思想是将主串中的后缀和模式串中的前缀对齐，然后进行比较后面的部分；

显然，主串和模式串在第六个位置时，处于失配状态，此时模式串中的前缀和后缀为 a b，将模式串的前缀和主串的后缀进行对齐，这样子的话就可以直接从模式串的第三个位置进行比较即可。整体思路就是上述所说的内容，然后需要解决的问题是如何找前缀和后缀所相等的最大长度，这里我们引入了数组next进行解决，
先解释一下next数组的作用： next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度+1。 第二个作用是说字符串不匹配时需要回溯的位置。
KMP算法的精髓在于next数组，首先解释next数组中的值代表的意义：
补充前缀和后缀的概念 eg：前缀指的是一串字符串中除了最后一个字符外的所有字符按照顺序排列的集合，字符串a b c d 他的前缀分别是{a}{a,b}{a,b，c};后缀指的是一串字符串中除了第一个字符外的所有字符按顺序排列的集合，字符串a,b,c,d他的后缀分别是{d}{c,d}{b,c,d};关于前缀和后缀的问题，CSDN有很多优质的博文去解释这个问题，我相信她们比我解释的好。
eg：a b a c next【4】指在第四元素之前的三个元素中，前缀和后缀相同的最大长度为1+1=2，所以next【4】=2；前缀和后缀相同的最大长度为1，但是得再加1，原因是要进行匹配，所以都得在最后加上1
next【0】数组没有实际意义，模式串的第一个字符从next【1】进行存储，当然next【0】也可以存放数组的长度
前缀用j表示，后缀用i表示；
小总结：在做求next【】的值时，总要在最大长度之后加上1
关于代码部分，总体思路是从中间取i,j的值，这样子可以更好的加深对代码的分析，我只能解释代码，不会写代码。注意此处取的不是特殊值，它反映的是已汇总普遍的现象。
eg：字符串a b a b a a a b a（字符之间没有空格，打空格是为了方便看）

假设起初i指向的是第三个元素，j将指向的是第一个元素，所以i指向的是字符a，j指向的是字符a；

（此处的i,j不是指针，使用箭头是方便认出）
很清楚的可以看出，此时i ，j分别指着两个a，a==a，表明字符串匹配成功，则继续下一个字符串的匹配，
此处的代码可以表示为：

if(next[i]==next[j])
{
	i++;
	j++;
	next[i]=j;
}
1
2
3
4
5
6

解释代码 next[i]=j;
因为执行完代码i++; j++;之后，此时i=4，j=2；next【4】=2；此处说明一下，前缀j是可以填充next【i+1】值的关键所在，j永远是从第一个字符串开始，j的改变说明这一串字符中有多少个相同的前缀和后缀,j往后移动一位，说明前缀和后缀相同的字符个数+1；而next【i】中存储的值永远表明在i之前的i-1字符中，前缀和后缀的相同字符串的数目。
i和j同步往后移，直到j=b，i=a时，此时next【j】！=next【i】，在此之前，匹配相同的字符串是aba


当遇到next【i】！= next【j】时，
代码：

else
{
	j=next[j];
}
1
2
3
4

此时j要进行回溯。
先解释一个结论：next[j+1]的最大值为next[j]+1
这个结论不懂也可以；后面举例说明：
要求next【17】的值，已知next【16】=8，说明前缀后缀最大重叠度为7，
若next【8】==next【16】，则next【17】=8+1=9

若next【8】！=next【16】，则j=next【j】；j回溯到next【8】，
假设next【8】==4；

根据对称性。所以可以得出：

所以可以得出：（荧光深蓝色部分相同）

若果next【4】==next【16】，继续执行 i++;j++;程序，若果next【4】！=next【16】；则按照上面的方法继续讨论；
按照这个样子以此类推，就可以得出next数组的值；
上述过程为next函数的大体框架，接下来介绍next数组的一些边角料；
代码：j=0;i=1;while循环判断的条件是while（i<next【0】）；此处next【0】的内容为字符串的串长，
总体代码：

void get_next(String T,int *next)
{
	i=0;j=1;
	next[1]=0;
	if(j=0||T[i]==T[j])
	{
		i++;
		j++;
		next[i]=j;
	}
	else
	{
		j=next[j];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

感谢 小甲鱼 哈顿之光 Sirm23333（借鉴）。