2. 计算机
  3. (2012年上半年上午试题58)在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为________。

(2012年上半年上午试题58)在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为________。

admin2021-01-13  62
问题 (2012年上半年上午试题58)在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为________。
选项 A、0123123
B、0123210
C、0123432
D、0123456
答案A
解析 j=1时，next[1]=0。j=2时，不存在k满足1＜k＜j，则next[2]=1。j=3时，k只能取2，等式的左边为p1，等式的右边为p2，p1=p2=a，next[3]=2。j=4时，k可以取2和3，k取2时，左边为p1，右边为p3，p1=p3=a；k取3时，左边为p1p2，右边为p2p3，p1p2=p2p3=aa；k取较大值3，因此next[4]=3。j=5时，k可以取2、3、2，k取2时，左边为p1=a，右边为p4=b，左右两边不等；k取3时，左边为p1p2=aa，右边为p3p4=ab，左右两边不等；k取4时，左边为p1p2p3=aaa，右边为p2p3p4=aaba，左右两边不等，因此next[5]：1。至此，可以判断正确答案为A。
转载请注明原文地址:https://kaotiyun.com/show/HXCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)