易懂"/>
简单易懂
1.next数组
序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] |
默认前两位是0和1
序号 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] | 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
序号 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] | 0 | 1 | 1 |
第4位,找前一个字母p[3],是a,next[3]=1.我们就看第1个字母,是a,与p[3]相等,那么就用next[3]+1,所以next[4]为1+1=2
序号 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] | 0 | 1 | 1 | 2 |
第5位,找前一个字母p[4],是b,next[4]=2,我们就看第2个字母,是b,与p[4]相等,那么就用next[4]+1,所以next[5]=3
序号 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] | 0 | 1 | 1 | 2 | 3 |
第6位,找前一个字母p[5],是c,next[5]=3,我们就看第3个字母,是a,与p[5]不相等,那就继续往前找,next[3]=1,我们就看第1个字母,是a,与p[5]还不相等,那么next[6],只能等于0+1=1了
序号 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] | 0 | 1 | 1 | 2 | 3 | 1 |
第7位,找前一个字母p[6],是a,next[6]=1,我们就看第1个字母,是a,与p[6]相等,那么next[7]=next[6]+1=2
序号 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] | 0 | 1 | 1 | 2 | 3 | 1 | 2 |
第8位,找前一个字母p[7],是b,next[7]=2,看第2个字母,是b,与p[7]相等,那么next[8]=next[7]+1=3
序号 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] | 0 | 1 | 1 | 2 | 3 | 1 | 2 | 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数组
序号 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
p[i] | a | b | a | b | c | a | b | c |
next[i] | 0 | 1 | 1 | 2 | 3 | 1 | 2 | 3 |
nextval[i] | 0 | 1 | 0 | 1 | 3 | 0 | 1 | 3 |
默认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];}}
}
更多推荐
简单易懂
发布评论