前言

在我们学习数据结构字符串的时候会遇到匹配问题，当然我们可以用简单匹配算法，但是为了追求效率我们还有KMP算法 而实现KMP算法是离不开next数组的。
今天我就来讲解一下next数组和进阶next数组nextval；

看此篇文章需要了解一下KMP算法，KMP算法在我另一篇博客里，可以先了解一下再来看；

一、next数组

在讲解之前我们要了解两个概念；
前缀和后缀
看一串字符：a b a b b c
若我们现在正在与主串比较第四个字符
有前缀 ：a ，ab ，aba（我们看真前缀-也就是不能等同于前面的字符串）所以aba我们就不看了
有后缀 ：a ，ba ，aba （aba不在考虑的范围）
next数组就是取最大相同前后缀字符个数加一；
那么正在匹配的 b 所对应的next[4]=最大相同前后缀字符个数加一=1+1=2；

1、next数组是什么

next数组是为了解决匹配过程中子串回溯的问题，如果每次都像简单匹配算法一样回溯到第一个字符的位置那未免效率太低了，我们看下面一张图：

上面一行是字符数组的下标，为了更能清楚的显示，我是用一开头，前面的第一位可以用来表示字符的个数；
可以看到下面一行就是next数组，数组里面的数的意思是–
当到第三位a不匹配时我们回溯到next数组所指向的哪一位，也就是第一位；
当我们到第五个不匹配时将回溯到第三位，这就是next数组，避免每次都回溯到第一位

2、求next数组

#define MAX 100
typedef struct stu {
	char arr[MAX];
	int length;
}Str;

void getnext(Str l, int* next)
{
	int i = 1,t=0;

	while (i < l.length)
	{
		if (i == 0)
		{
			next[i] =0 ;
		}
		if (t == 0 || l.arr[i] == l.arr[t])
		{
			next[i + 1] = t + 1;
			i++;
			t++;
		}
		else
		{
			t = next[t];
		}
	}
}
//这里我用字符串的第一位表示字符串的个数，这样更方便；

这就是求得next数组的完整代码，

二 、nextval数组

1、nextval数组是什么？

我们知道KMP算法中主串永远不回溯，所以我们需要保证在next数组所指向的回溯位置不能与之前位置上的字符相同，如下图

可以看到下面一串数字就是nextval数组

当到达第四个字符 a 时发生了不匹配，若运用next数组回到第一位，由于主串永远不回溯则在第一位上的 a 与主串当前位置上的字符也会不匹配，为了避免这种情况则有了nextval数组；

2、求nextval数组

#define MAX 100

typedef struct stu {
	char arr[MAX];
	int length;
}Str;

void getnextval(Str l, int* nextval,int* next)
{
	int i = 1, t = 0;
	nextval[1] = 0;
	while (i < l.length)
	{
		if (t == 0 || l.arr[t] == l.arr[i])
		{
			next[i+1]= t + 1;
			if (l.arr[i + 1] != l.arr[next[i + 1]])
			{
				nextval[i + 1] = next[i+ 1];
			}
			else
			{
				nextval[i + 1] = next[next[i + 1]];
			}
			t++;
			i++;
		}
		else
		{
			t = next[t];
		}
	}
}

对比两个数组的求法会发现变化并不大；

总的来说，next数组是为了求得KMP算法，加大运行的效率；