大家好,欢迎来到IT知识分享网。
nextval数组求解过程
为什么用nextval数组
next数组在某些情况下仍存在缺陷,例如 模式串”aaaab”与主串”aaabaaaab”进行匹配时:
主串下标为0时的next数组为:
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
主串 S | a | a | a | b | a | a | a | a | b |
模式串 T | a | a | a | a | b | ||||
next[ ] | -1 | 0 | 1 | 2 | 3 |
主串下标为1时的next数组为:
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
主串 S | a | a | a | b | a | a | a | a | b |
模式串 T | a | a | a | a | b | ||||
next[ ] | 0 | 1 | 2 | 3 | 4 |
无论哪种方式,当匹配到第四位,主串为b,模式串是a,两者不相同,则主串b需要依次跟第三位a,第二位a,第一位a依次作对比,实际上,前三位与第四位都相同,显然与前三位的比较没有意义,一定会匹配失败。
nextval数组是对next数组进行的该进,减少这种无意义的比对。
nextval数组求解方式
已知串T=“ababaaababaa”;
利用next数组求nextval数组
下面从代码的角度讲述一下求解nextval[]的思路:
1、可以确定nextval的第一位与next数组第一位相同
2、从第二位开始,依次判断该位置的next值对应的元素与该位置元素是否相同,
3、若相同,该位置的nextval的值就是该位置next值对应元素的nextval的值
4、若不同,该位置的nextval的值就是该位置的next值
IT知识分享网
一、模式串的下标从0开始,nextval数组求解方式详解:
1、可以确定第一位的值:nextval[0] = next[0] = -1;
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 |
2、看第二位,也就是T[1] = b,T[1]next所对应的元素是T[0] = a,b与a不同,则T[1]的nextval的值就是T[1]的next值,nextval[1] = next[1] = 0
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 |
3、看第三位,也就是T[2] = a,T[2]next所对应的元素是T[0] = a,a与a相同,则T[2]的nextval的值就是T[2]next对应元素的nextval的值: nextval[next[2]] = nextval[0] = -1
即:nextval[2] = nextval[0] = -1
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 |
4、看第四位,也就是T[3] = b,T[3]next所对应的元素是T[1] = b,b与b相同,则T[3]的nextval的值就是T[3]next对应元素的nextval的值: nextval[next[3]] = nextval[1] = 0即:nextval[3] = nextval[1] = 0
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 |
5、看第五位,也就是T[4] = a,T[4]next所对应的元素是T[3] = a,a与a相同,则T[4]的nextval的值就是T[4]next对应元素的nextval的值 是 nextval[next[4]] = nextval[2] = -1
即:nextval[4] = nextval[2] = -1
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 | -1 |
6、看第六位,也就是T[5] = a,T[5]next所对应的元素是T[3] = b,a与b不同,则T[5]的nextval的值就是T[5]next值,nextval[5] = next[5] = 3
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 | -1 | 3 |
7、看第七位,也就是T[6] = a,T[6]next所对应的元素是T[1] = b,a与b不同,则T[6]的nextval的值就是T[6]next值,nextval[6] = next[6] = 1
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 | -1 | 3 | 1 |
8、看第八位,也就是T[7] = b,T[7]next所对应的元素是T[1] = b,b与b相同,则T[7]的nextval的值就是T[7]next对应元素的nextval的值 是 nextval[next[7]] = nextval[1] = 0
即:nextval[7] = nextval[1] = 0
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 | -1 | 3 | 1 | 0 |
9、看第九位,也就是T[8] = a,T[8]next所对应的元素是T[2] = a,a与a相同,则T[8]的nextval的值就是T[8]next对应元素的nextval的值 是 nextval[next[8]] = nextval[2] = -1
即:nextval[8] = nextval[2] = -1
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 | -1 | 3 | 1 | 0 | -1 |
10、看第十位,也就是T[9] = b,T[9]next所对应的元素是T[3] = b,b与b相同,则T[9]的nextval的值就是T[9]next对应元素的nextval的值 是 nextval[next[9]] = nextval[3] = 0
即:nextval[9] = nextval[3] = 0
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 | -1 | 3 | 1 | 0 | -1 | 0 |
11、看第十一位,也就是T[10] = a,T[10]next所对应的元素是T[5] = a,a与a相同,则T[10]的nextval的值就是T[10]next对应元素的nextval的值 是 nextval[next[10]] = nextval[4] = -1
即:nextval[10] = nextval[4] = -1
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 | -1 | 3 | 1 | 0 | -1 | 0 | -1 |
12、看第十二位,也就是T[11] = a,T[11]next所对应的元素是T[5] = a,a与a相同,则T[11]的nextval的值就是T[11]next对应元素的nextval的值 是 nextval[next[11]] = nextval[5] = 3
即:nextval[11] = nextval[5] = 3
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
nextval[ ] | -1 | 0 | -1 | 0 | -1 | 3 | 1 | 0 | -1 | 0 | -1 | 3 |
代码实现
IT知识分享网void getNextval(char T[],int TLength) {
int nextval[TLength];
nextval[0] = -1;
printf("next[0] = %d \n", nextval[0]);
int i = 0, j = -1; //i表示下标,初始化为0;j表示nextval数组的值,初始化为-1
while (i < TLength-1) {
if (j == -1 || T[i] == T[j]) {
i++;
j++;
if(T[i] != T[j]) {
//不同,该位置的nextval的值就是该位置的next值
nextval[i] = j;
printf("nextval[%d] = %d \n", i, nextval[i]);
} else{
//相同,该位置的nextval的值就是该位置next值对应元素的nextval的值
nextval[i] = nextval[j];
printf("nextvl[%d] = %d \n", i, nextval[i]);
}
}else{
j = nextval[j] ;
}
}
}
int main(){
char T[] = {
'a','b','a','b','a','a','a','b','a','b','a','a'};
int TLength = 12;
getNextval(T,12);
eturn 0;
}
测试结果:
nextval[0] = -1
nextval[1] = 0
nextvl[2] = -1
nextvl[3] = 0
nextvl[4] = -1
nextval[5] = 3
nextval[6] = 1
nextvl[7] = 0
nextvl[8] = -1
nextvl[9] = 0
nextvl[10] = -1
nextvl[11] = 3
二、模式串的下标从1开始,nextval数组求解方式详解:
1、可以确定第一位的值:nextval[1] = next[1] = 0;
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
2、看第二位,也就是T[2] = b,T[2]next所对应的元素是T[1] = a,b与a不同,则T[2]的nextval的值就是T[2]的next值,nextval[2] = next[2] = 1
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
3、看第三位,也就是T[3] = a,T[3]next所对应的元素是T[1] = a,a与a相同,则T[3]的nextval的值就是T[3]next对应元素的nextval的值: nextval[next[3]] = nextval[1] = 0
即:nextval[3] = nextval[1] = 0
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
4、看第四位,也就是T[4] = b,T[4]next所对应的元素是T[2] = b,b与b相同,则T[4]的nextval的值就是T[4]next对应元素的nextval的值: nextval[next[4]] = nextval[2] = 1
即:nextval[4] = nextval[2] = 1
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
5、看第五位,也就是T[5] = a,T[5]next所对应的元素是T[3] = a,a与a相同,则T[5]的nextval的值就是T[5]next对应元素的nextval的值 是 nextval[next[5]] = nextval[3] = 0
即:nextval[5] = nextval[3] = 0
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
6、看第六位,也就是T[6] = a,T[6]next所对应的元素是T[4] = b,a与b不同,则T[6]的nextval的值就是T[6]next值,nextval[6] = next[6] = 4
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
7、看第七位,也就是T[7] = a,T[7]next所对应的元素是T[2] = b,a与b不同,则T[7]的nextval的值就是T[7]next值,nextval[7] = next[7] = 2
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
8、看第八位,也就是T[8] = b,T[8]next所对应的元素是T[2] = b,b与b相同,则T[8]的nextval的值就是T[8]next对应元素的nextval的值 是 nextval[next[8]] = nextval[2] = 1
即:nextval[8] = nextval[2] = 1
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
9、看第九位,也就是T[9] = a,T[9]next所对应的元素是T[3] = a,a与a相同,则T[9]的nextval的值就是T[9]next对应元素的nextval的值 是 nextval[next[9]] = nextval[3] = 0
即:nextval[9] = nextval[3] = 0
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
10、看第十位,也就是T[10] = b,T[10]next所对应的元素是T[4] = b,b与b相同,则T[10]的nextval的值就是T[10]next对应元素的nextval的值 是 nextval[next[10]] = nextval[4] = 1
即:nextval[10] = nextval[4] = 1
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
11、看第十一位,也就是T[11] = a,T[11]next所对应的元素是T[5] = a,a与a相同,则T[11]的nextval的值就是T[11]next对应元素的nextval的值 是 nextval[next[11]] = nextval[5] = 0
即:nextval[11] = nextval[5] = 0
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
12、看第十二位,也就是T[12] = a,T[12]next所对应的元素是T[6] = a,a与a相同,则T[12]的nextval的值就是T[12]next对应元素的nextval的值 是 nextval[next[12]] = nextval[6] = 4
即:nextval[12] = nextval[6] = 4
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
模式串 T | 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 |
代码实现
IT知识分享网void getNextval(char T[],int TLength) {
int nextval[TLength];
nextval[1] = 0;
printf("nextval[1] = %d \n", nextval[1]);
int i = 1, j = 0; //i表示数组下标,初始化为1;j表示next数组的值,初始化为0
while (i < TLength-1) {
if (j == 0 || T[i] == T[j]) {
i++;
j++;
if(T[i] != T[j]) {
//不同,该位置的nextval的值就是该位置的next值
nextval[i] = j;
printf("nextval[%d] = %d \n", i, nextval[i]);
} else{
//相同,该位置的nextval的值就是该位置next值对应元素的nextval的值
nextval[i] = nextval[j];
printf("nextval[%d] = %d \n", i, nextval[i]);
}
}else{
j = nextval[j] ;
}
}
}
int main(){
char T[] = {
'*','a','b','a','b','a','a','a','b','a','b','a','a'};
int TLength = 13;
getNextval(T,13);
return 0;
}
测试结果:
nextval[1] = 0
nextval[2] = 1
nextval[3] = 0
nextval[4] = 1
nextval[5] = 0
nextval[6] = 4
nextval[7] = 2
nextval[8] = 1
nextval[9] = 0
nextval[10] = 1
nextval[11] = 0
nextval[12] = 4
注意:这两种方式的细微差别,整体思路一致,注意nextval起始位置以及边界条件,根据自己实际情况选择
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/7547.html