nextval数组求解「建议收藏」

nextval数组求解「建议收藏」nextval数组求解过程为什么用nextval数组nextval数组求解方式一、模式串的下标从0开始,nextval数组求解方式详解:代码实现二、模式串的下标从1开始,nextval数组求解方式详解:代码实现为什么用nextval数组next数组在某些情况下仍存在缺陷,例如模式串”aaaab”与主串”aaabaaaab”进行匹配时:主串下标为0时的next数组为:下标012345678主串Saaabaaaab模式串Taaaa

大家好,欢迎来到IT知识分享网。

为什么用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

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信