先计算前缀next[i]的值： （字符串匹配是 从头开始的 和 从尾开始的字符串进行匹配是否重复 ）

next[i]的值主要是看s[i]之前的字符串中重复的子串长度。next[0] = -1，定值。

next[1]是看s[1]之前的字符串“a”中重复的子串长度为0，故next[1] = 0。

next[2]是看s[2]之前的字符串“ab”中重复的子串长度为0，故next[2] = 0。

next[3]是看s[3]之前的字符串"aba"中重复的子串长度，s[0]与s[2]重复，长度为1，故next[3] = 1。

next[4]是看s[4]之前的字符串"abab"中重复的子串长度，s[01]与s[23]重复，长度为2，故next[4] = 2。

next[5]是看s[5]之前的字符串"ababa"中重复的子串长度，s[012]与s[234]重复，长度为3，故next[5] = 3。

next[6]是看s[6]之前的字符串"ababaa"中重复的子串长度，s[0]与s[5]重复(因为多了一个a，无法找到长度为3的重复字符串，这只能是s[0]和s[5]重复)，长度为1，故next[6] = 1。

同样的，求next[7]和next[8]、next[9]、 next[10]、 next[11] 分别为1和2、3、4、5。

总结：

1、next数组首个位置数值为定值-1

2、next[i]的值是看在s[i]之前的字符串中重复的子串长度（1、不统计第i位置的字符2、两个子串一个必须从首位置开始，另一个必须从尾位置结束）

一、next数组(简单易懂)

next函数值仅取决于模式串本身，与主串无关

next数组的生成这里有两种方式：
1.前缀后缀匹配
2.字符串下标匹配
以一个数组为例：
a b a b a a a b a b a a 
我们要生成这个模式串的next数组，那么首先第一件事就是为这些字符标号，
如下；

  序号j: 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a

方法一 前缀后缀匹配

1. 前缀和后缀进行比较，如果前缀和后缀没有相同前缀，则为0+1，如果相同，则相同的字符个数+1；
2. 前缀取s[n]之前字符的n-2位，后缀取s[n]之前n-1字符后面的后n-2位。

  序号j: 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a
 next[]: 0 1
 1.next[1],next[2]无论是什么模式串数组，永远都是0和1。
 
 2.next[3]：如上，序号j[3]对应的模式串s[3]，那么我们就看模式串s[3]前面的
 字符即可，即为a b,那么s[3]的前缀为a,后缀为b,a和b不相同,则next[3]为0+1=1;
 
 3.next[4]:序号j[4]对应的s[4],找s[4]的前面字符，为a b a,字符前缀为a、ab；
 后缀为ba, a;有1个相同字符，则next[4]=1+1=2;

 4.next[5]:序号j[5]对应的s[5],找s[5]的前面字符，为a b a b,字符前缀为a、ab
 aba三个，后缀为bab、ab、b三个，进行比较，有字符串ab相同，则next[5]=2+1=3

 以此类推......

 5.next[12]:序号j[12]对应的模式串字符为s[12],取前n-1个字符，为a b a b a a a b a b a,前缀为：ababaaabab,后缀为babaaababa.
 可看出前缀中 ababa与后缀中ababa5个字符相同，则next[12]=5+1=6;

最终生成的next字符串为：

    j: 1 2 3 4 5 6 7 8 9 10 11 12
    s: a b a b a a a b a b  a  a
 next: 0 1 1 2 3 4 2 2 3 4  5  6

方法二 字符串下标匹配

  序号j: 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a
 next[]: 0 1 1 2 3 4 2 2 3 4  5  6
 1.next[1],next[2]无论是什么模式串数组，永远都是0和1。
 
 2.next[3]：我们要生成next[3]的值，就要先看前一位s[2]对应的next值为1,那么
 以对应的next值1为下标，s[1]与s[2]比对，不相同，则next[3]为0+1=1。
 
 3.next[4]:要生成next[4],首先要看前一位s[3]对应的next值为1，则以对应的
 next值为下标，s[3]不变,s[1]为a,s[3]也为a,相同，则以s[3]下标1进行加一，为
 1+1=2,所以，next[3]=2;
 
 4.next[5]，next[6]:同理。next[5]=3,next[6]=4
 
 5.next[7]:到这就有问题了，前一位s[6]所对应的next下标为4，所以，s[6]和s[4]对比，不相同！那么，继续看s[4]所对应的next下标，
 为2，s[6]不动，永远作为对比方，与s[4]对应next下标数字为序号再次进行对比，以此类推，s[2]=b,
 s[6]=a,不相同！继续操作，s[2]的next值为1，以是s[1]为下标，继续对比，s[1]=s[6]=a.到此为止,next[7]的值为s[2]的next值+1，为2.
 
 6.后面同理。
 

二、nextval（有手就行）

这里我们只介绍最简单的生成nextval数组的方法，nextval数组第一个字符永远为0。
既然我们上面生成了next数组，nextval数组直接通过next数组便可生成。
若不同，填入next的值；若相同，填入该值对应的序号的nextval.

   序号 : 1 2 3 4 5 6 7 8 9 10 11 12
 模式串s: a b a b a a a b a b  a  a
  next[]: 0 1 1 2 3 4 2 2 3 4  5  6
 nextval: 0 
 
 1.nextval[1]=0,默认值
 2.nextval[2]：s[2]对应的next值为1，则以1为下标s[1],与s[2]进行对比,不相同，
 则将s[2]对应的next值直接下发到nextval，nextval[2]=next[2]=1;
 3.nextval[3]：s[3]对应的next值为1，则以1为下标，与s[3]进行对比，相同，则nextval[3]=nextval[1]=0;
 4.nextval[4]：s[4]对应的next值为2,则以2为下标,与s[4]进行对比，相同，则nextval[4]=nextval[1]=0;
 5.依次同理.....
 6.nextval[12]:s[12]对应的next值为6，则s[6]与s[12]对比,相同，则nextval[12]=nextal[6]=4;
 
 最终生成的nextval为：
   序号 : 1 2 3 4 5 6 7 8 9 10 11 12
 模式串s: a b a b a a a b a b  a  a
  next[]: 0 1 1 2 3 4 2 2 3 4  5  6
 nextval: 0 1 0 1 0 4 2 1 0 1  0  4

//朴素算法
//s主串，t字串，pos初始为1
//返回第pos个位置之后有字串，无则返回0
int Index(String* s, String* t, int pos) {
	if (pos<1 || pos>s->length - t->length + 1) {
		printf("输入有误");
	}
	int i = pos; //i用于主串的位置
	int j = 0;   //j用于子串的位置
	while (i <= s->length && j <= t->length) {
		if (s[i - 1] == t[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 1;
			j = 0;
		}
	}
	if (j == t->length) {
		return i - t->length;
	}
	else {
		return 0;
	}
}

//next数组
int get_next(String* t, int* next) {
	int i, j;
	i = 1;
	j = 0;
	next[1] = 0;
	while (i < t->length) {
		if (j == 0 || t[i] == t[j]) {
			++i;
			++j;
			next[i] = j;
		}
		else {
			j = next[j];
		}
	}
}


//nextval数组
void get_nextval(String* t, int* nextval) {
	int i, j;
	i = 1;
	j = 0;
	nextval[1] = 0;
	while (i < t->length) {
		if (j == 0 || t[i] == t[j]) {
			++i;
			++j;
			if (t[i] == t[j]) {
				nextval[i] = nextval[j];
			}
			else {
				nextval[i] = j;
			}
		}
		else {
			j = nextval[j];
		}
	}
}

这些代码很好看懂，却没办法轻易‘看’懂。其实在看到这段代码的时候，我满头问号，直呼凭什么，自己试着琢磨了一段时间，最后还是去搜了相关的讲解视频。

其实画一个图，一切的问题就会变得简单很多。