【数据结构与算法学习笔记二十一】kmp中nextvar的求法

求nextval数组值的第二种方法

模式串 a b a a b c a c
next值 0 1 1 2 2 3 1 2
nextval值 0 1 0 2 1 3 0 2

1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。
       2.第三位的next值为1,那么将第三位和第一位进行比较,均为a,相同,则,第三位的nextval值为0
       3.第四位的next值为2,那么将第四位和第二位进行比较,不同,则第四位的nextval值为其next值,为2。
       4.第五位的next值为2,那么将第五位和第二位进行比较,相同,第二位的next值为1,则继续将第二位与第一位进行比较,不同,则第五位的nextval值为第二位的next值,为1。
       5.第六位的next值为3,那么将第六位和第三位进行比较,不同,则第六位的nextval值为其next值,为3。
       6.第七位的next值为1,那么将第七位和第一位进行比较,相同,则第七位的nextval值为0。
       7.第八位的next值为2,那么将第八位和第二位进行比较,不同,则第八位的nextval值为其next值,为2。
       在“aaaab”内进行验证。

模式串 a a a a b
next值 0 1 2 3 4
nextval值 0 0 0 0 4

 

思想:

1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。

1.next的值说明了比较的对象

2.如果比较的结果是不同,则自身nextval的值就是自身next的值

3.如果比较的结果相同,那么再由它的前驱去比较,不同的话,前驱的next的值就是他的nextval的值,如4,相同的话,再比较,直到到头(为0)或者不同。

发表评论

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