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

admin2021-01-13  32

问题 (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)