首页 > 试题广场 >

用KMP算法,求串eefegefeef的next值和next

[问答题]

用KMP算法,求串eefegefeef的next值和nextval值,写出计算过程。

模式串 eefegefeef
next数组
0121212123
nextval数组
0020202002


发表于 2018-06-13 16:28:07 回复(0)
下标 1 2 3 4 5 6 7 8 9 10
模式串 e
e f e g e f e e f
next数组 0 1 2 1 2 1 2 1 2 3
nextval数组 0 0 2 0 2 0 2 0 0 2
(默认数组从1开始的结果为上图,如果为0的话,结果为所有值减1)
next数组求法:当模式串的i位匹配失败时,在它之前的i-1子串求最长相等前后缀长度+1,前缀长度指的是模式子串包含第一个字母的前n个字母组成的串,后缀长度类同,就是包含最后一个字母的后n个字母组成的串,找到相同的前后缀串的长度+1就是对应next数组的值,比如表格中的最后一个f,他的i-1子串为eefegefee,我们找到他相等的前后缀为ee,ee的长度为2,所以最后一个f对应的next数组的值就为2+1=3。
nextval数组的求法:在next数组的基础上,如果next j是同样字符,则把下标小的next值赋值给下标大的next值。

发表于 2021-02-19 23:42:05 回复(0)
发表于 2020-04-29 16:25:28 回复(0)
kmp看毛片!
发表于 2017-02-22 02:42:19 回复(0)