简单易懂

易懂"/>

简单易懂

1.next数组

默认前两位是0和1

第3位开始,找它前一个的字母p[2]，也就是b，b的next[i]是1，所以我们就看第1个字母与p[2]是否相同，相同就用p[2]的next[i]+1，不相同就继续往前找，这里不相同，我们就继续往前找，如何找呢？当人是根据第next[2]个字母的next[i]，已经是0了，说明没有匹配的，那么next[3]的值就为0+1=1

第4位，找前一个字母p[3]，是a，next[3]=1.我们就看第1个字母，是a,与p[3]相等,那么就用next[3]+1,所以next[4]为1+1=2

第5位，找前一个字母p[4]，是b，next[4]=2，我们就看第2个字母，是b，与p[4]相等，那么就用next[4]+1,所以next[5]=3

第6位，找前一个字母p[5]，是c，next[5]=3，我们就看第3个字母，是a，与p[5]不相等，那就继续往前找，next[3]=1，我们就看第1个字母，是a，与p[5]还不相等，那么next[6]，只能等于0+1=1了

第7位，找前一个字母p[6]，是a,next[6]=1,我们就看第1个字母，是a，与p[6]相等，那么next[7]=next[6]+1=2

第8位，找前一个字母p[7]，是b,next[7]=2,看第2个字母，是b，与p[7]相等，那么next[8]=next[7]+1=3

代码实现:

void get_next(SString T, int next[])
{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];}
}

2.nextval数组

默认nextval[1]=0

求nextval数组，用p[i]与p[next[i]]比较，如果相等，nextval[i]=nextval[next[i]],否则等于next[i]

举例说明:

第2位是b，next[2]是1，第1位是a,a与b不相等，故nextval[2]=next[2]=1

第3位是a， next[3]是1.第1位是a，a与a相等，故nextval[3]=nextval[next[3]]=nextval[1]=0

第4位是b，next[4]是2，第2位是b，b与b相等，故nextval[4]=nextval[next[4]]=nextval[2]=1

第5位是c，next[5]是3,第3位是a，a与c不相等，故nextval[5]=next[5]=3

以此类推，得到nextval数组为 0 1 0 1 3 0 1 3

代码实现:

void get_nextval(SString T, int nextval[]){int i = 1;int j = 0;nextval[1] = 0;while (i < T[0]){if (j==0 || T[i]==T[j]){++i;++j;if (T[i] != T[j])nextval[i] = j;elsenextval[i] = nextval[j];}else{i = nextval[j];}}
}