背景：本篇博客是博主学习B站视频#小马xiao_ma和#凡三岁爱学习后的学习笔记，如果你只是应付考试只需观看前者的视频，如果你想详细了解代码过程不妨看看第二个链接里UP的视频和我的博客。该博客的详细解释完全适用于严蔚敏老师的数据结构课程书。

注意： 

• 无论是以上两位UP的视频还是本篇博客，数组的起始位置都是从1开始。
• 我们计算的均是模式串的next[]数组和nextval[]数组。当字符不匹配时模式串回退到next[j]或是nextval[j]的位置，而主串不回退。

问题重述 ：在字符串匹配算法中，由于BF算法里，当发生不匹配时主串需要返回到 i-j+2的位置，而模式串则需要返回到1的位置，所以整个算法的时间复杂度为O(m*n)。我们尝试改进算法使其的时间复杂度为O(m+n)即KMP算法。

基本概念：

• 前缀：包括首位字符单不包括末尾字符的子串。
• 后缀：包括末位字符但不包括首位字符的字串。
• next[]数组的定义：当主串与模式串的某一个字符不匹配时，模式串要回退的位置。
• next[j]：其值=第 j位字符前面 j -1位字符组成的子串的前后缀重复字符数+1。

由基本概念推导得：

• next[]数组的第一位必为0，第二位必为1，且next[]数组的值与模式串的最后一个字符无关。
• next[j+1]的最大值为next[j]+1。
• 如果，那么next[j+1]可能的次最大值为next[ next[j ] ]+1，以此类推即可高效退出next[j+1]。

流程：

1. 求next[j+1]，则默认已知next[1]、next[2]、......next[j]。
2. 假设next[j]=k1，则有...=...（前k1-1个字符）与后k1-1个字符重复相等
3. 如果，则，则next[j+1]=k1+1。否则进入下一步(4)
4. 假设next[k1]=k2，则有
5. 由第二和第四步联立可得：即四段相等
6. 这个时候，再判断如果，则，则next[j+1]=k2+1; 否则再取next[k2]=k3...以此类推。

图解:  

图一第二步：

这个时候如果发生不匹配即（红方块值不相等），那我们这时就想找到前面第二长相同的前后缀。等价于我们想找前面最长的相同前后缀。于是我们将取next[k1]=k2；

图二第四步：

我们已经通过next[k1]找到了第二长的相同前后缀，这时我们判断是否等于。如果是则next[j+1]=next[k1]+1;如果不是则我们通过next[k2]找到第三长的相同前后缀，继续判断是否等于。以此类推若一直判断不相等我们最终将判断和的值是否相等，若还是不相等则的值为1。

以下是求next[]数组的具体代码：

#include<iostream>
#include<string>
using namespace std;

void get_next(string str,int next[])
{
	int i = 1;
	int j = 0;
	next[1] = 0;
	while (i < str.length()-1)//这里的长度可根据自己的实际情况而定
	{
		if (j == 0 || str[i] == str[j])
			next[++i] = ++j;
		else j = next[j];
	}
}

void print(int next[],int n)
{
	for (int i = 1; i <= n; i++)
		cout << next[i];
}

int main()
{
	string str = " ababaaababaa";//注意这里第一个字符为空，是为了下标从1开始
	int* next = new int[str.length()+1];
	get_next(str,next);
	print(next, str.length());
	return 0;
}

程序输出结果为：011234223456

以上为求next[]数组的方法，但next[]数组有一个缺陷。假设与相等且模式串在j+1的位置与主串发生了不匹配，那么按道理模式串此时应该回退的位置为k+1。但如果此时与相等，则模式串需要继续回退。举书本上的例子：主串为：“aaabaaaab”，模式串为：“aaaab”。主串的第四个字符'b'与模式串的第四个字符'a'发生了不匹配，根据next[]数组的值，模式串会返回到第三个字符'a'的位置，a仍然等于a，也就是发生了我们刚才提到的。综上我们希望一步返回到的位置。以下是改进后nextval[]数组详细代码。

void get_nextval(string str, int nextval[])
{
	int i = 1;
	int j = 0;
	nextval[1] = 0;
	while (i < str.length() - 1)//这里的长度可根据自己的实际情况而定
	{
		if (j == 0 || str[i] == str[j])
		{
			i++, j++;
			if (str[i] != str[j])
				nextval[i] = j;
			else nextval[i] = nextval[j];
		}
		else j = nextval[j];
	}
}

即当时，判断是否等于。这里可能大家会有一个疑惑，按照上面的例子我不应该写一个while循环吗？有这个想法是好的，其实我们nextval[]数组的值是从前向后递推。即前面的nextval的值已经帮我们记住了不等于的位置。

如果你觉得本篇博客对你有帮助，麻烦给个小红心，感谢！