【数据结构】next 数组（详细求法）

话不多说，咱们直接通过问题来分析next数组该怎么求

Question：

设模式串"abcaababc"，求它的next函数值

① 首先，我们要从左向右看，第一个字符的next[ j ]永远是0，第二个字符的next[ j ]永远是1，所以在这里，第一个字符 a 的next[ j ]是0，第二个字符 b 的next[ j ]是1，然后继续往后看，第三个字符是 c，c前面一个字符 b 的next[ j ]是1，通过1我们找到了 a，a不等于b，所以 c 的next[ j ]值是1，如下图：

② 我们继续向右，第四个字符是a，我们看第四个字符a前面的那个字符，在这里是c，然后我们看c的next[ j ]值，c的next[ j ]值为1，通过c的next[ j ]值1，我们找到了 j 为1时的模式串 t，为 a，我们发现它和c不相等，并且此时已经无法再向前寻找了，所以此时我们令第四个字符的next[ j ]为 1，如下图：

③ 我们继续向右，第五个字符是a，第五个字符前面一个字符（即第四个字符a）的next[ j ]为1，通过 j = 1，我们找到模式串 t 为 a，发现它和第四个字符（a）相等，那么我们就在第四个字符的next[ j ]值基础上加上1，就是第五个字符的next[ j ]值，如下图：

④ 我们继续向右，第六个字符是b，我们看它前面的那个字符 a 的next[ j ]值，顺着 a 的next[ j ]值我们找到了 b，此时 b 和 a 不相等，我们再向前寻找，再向前寻找的时候我们是通过 b的next[ j ]值进行寻找，所以我们找到了 a，注意找到的 a 还是和我们的第五个字符作比较（向前寻找始终是和要求字符的前一个字符作比较），相同，所以在第二个字符的next[ j ]基础上加上1即可，如下图： 

⑤ 我们继续向右，第七、八、九个字符同理即可，如下图：

next数组具体算法实现：

注意：这个算法算出来的每个next数组值都要比上面的理论值小1。

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SIZE 128
#define INC 10
typedef struct String{
	char *data;
	int len;
	int size;
}String,*PString;
int Init_String(PString S){
	S->data=(char *)malloc(sizeof(char)*SIZE);
	S->len=0;
	S->size=SIZE;
	return 1;
}
int Creat_String(PString S,char *s){
	int i=0,n;
	n=strlen(s);
	while(*s!='\0'){
		if(S->size<n){
			S->data=(char *)realloc(S->data,(S->size+INC)*sizeof(char));
			S->size+=INC;
		}
		S->data[i++]=*s++;
		S->len++;
	}
	return 1;
}
void getNext(PString t,int next[]){      //next数组
	int i=0,j=-1;
	next[0]=-1;
	while(i<t->len){
		if(j==-1||(t->data[i]==t->data[j])){
			i++;
			j++;
			next[i]=j;
		}else{
		    j=next[j];	
		}
	}
	for(i=0;i<t->len;i++){
		printf("%d ",next[i]);
	}
}
int main(){
    String S;
    Init_String(&S);
    char s[100];
    int next[100];
    gets(s);
    Creat_String(&S,s);
    getNext(&S,next);
    return 0;
}