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，如下图：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 模式串 t | a | b | c | a | a | b | a | b | c |
| next [ j ] | 0 | 1 | 1 |
② 我们继续向右，第四个字符是a，我们看第四个字符a前面的那个字符，在这里是c，然后我们看c的next[ j ]值，c的next[ j ]值为1，通过c的next[ j ]值1，我们找到了 j 为1时的模式串 t，为 a，我们发现它和c不相等，并且此时已经无法再向前寻找了，所以此时我们令第四个字符的next[ j ]为 1，如下图：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 模式串 t | a | b | c | a | a | b | a | b | c |
| next [ j ] | 0 | 1 | 1 | 1 |
③ 我们继续向右，第五个字符是a，第五个字符前面一个字符（即第四个字符a）的next[ j ]为1，通过 j = 1，我们找到模式串 t 为 a，发现它和第四个字符（a）相等，那么我们就在第四个字符的next[ j ]值基础上加上1，就是第五个字符的next[ j ]值，如下图：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 模式串 t | a | b | c | a | a | b | a | b | c |
| next [ j ] | 0 | 1 | 1 | 1 | 2 |
④ 我们继续向右，第六个字符是b，我们看它前面的那个字符 a 的next[ j ]值，顺着 a 的next[ j ]值我们找到了 b，此时 b 和 a 不相等，我们再向前寻找，再向前寻找的时候我们是通过 b的next[ j ]值进行寻找，所以我们找到了 a，注意找到的 a 还是和我们的第五个字符作比较（向前寻找始终是和要求字符的前一个字符作比较），相同，所以在第二个字符的next[ j ]基础上加上1即可，如下图：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 模式串 t | a | b | c | a | a | b | a | b | c |
| next [ j ] | 0 | 1 | 1 | 1 | 2 | 2 | 3 |
⑤ 我们继续向右，第七、八、九个字符同理即可，如下图：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 模式串 t | a | b | c | a | a | b | a | b | c |
| next [ j ] | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 2 | 3 |
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; }
