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

admin2021-01-13 52

问题 (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，等式的左边为p₁，等式的右边为p₂，p₁=p₂=a，next[3]=2。j=4时，k可以取2和3，k取2时，左边为p₁，右边为p₃，p₁=p₃=a；k取3时，左边为p₁p₂，右边为p₂p₃，p₁p₂=p₂p₃=aa；k取较大值3，因此next[4]=3。j=5时，k可以取2、3、2，k取2时，左边为p₁=a，右边为p₄=b，左右两边不等；k取3时，左边为p₁p₂=aa，右边为p₃p₄=ab，左右两边不等；k取4时，左边为p₁p₂p₃=aaa，右边为p₂p₃p₄=aaba，左右两边不等，因此next[5]：1。至此，可以判断正确答案为A。

转载请注明原文地址:https://kaotiyun.com/show/HXCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

阅读下列说明，回答问题。【说明】现有事务T1，T2、L3它们对数值型数据A执行的操作分别如下：T1；将A加1。T2：将A加倍。T3：输出A的值，并将A置为1。

阅读以下说明和Java代码，将应填入(n)处的字句写在对应栏内。【说明】某绘图系统存在point、line、square三种图元，它们具有Shape接口，图元的类图关系如图13-12所示。现要将circle图元加入此绘图系统以实现功能扩充。已知

阅读以下说明和C++代码(代码13-1)，将应填入(n)处的字句写在对应栏内。【说明】软件设计师东方飞龙利用UML设计了一个迷你小型复数类，其类图如图13-11所示。【代码13-l】/*________________________

阅读下列算法说明和流程图，根据要求回答问题1～问题3。[说明]某机器上需要处理n个作业job1，job2，…，jobn，其中：(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值P[i]和最后期限值d[i]；

根据说明中的描述，使用表3-11给出的用例名称，给出图3-22中U1、U2和U3所对应的用例。简要解释图3-22中用例U1和U3之间的extend关系的内涵。

根据说明中的描述，使用表3-11给出的用例名称，给出图3-22中U1、U2和U3所对应的用例。根据说明中的描述，使用表3-11给出的状态名称，给出图3-24中S1～S4所对应的状态。

阅读下列函数说明和Java代码，将应填入(n)处的字句写在对应栏内。【说明】类Queue表示队列，类中的方法如下表所示。类Node表示队列中的元素；类EmptyQueueException给出了队列操作中的异常处理操作。p

阅读下列说明和C程序，将应填入(n)处的字句写在对应栏中。[说明]借助一个栈结构，可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历，遍历过程如下：若不是空树，根节点入栈，进入左子树；若已

囊肿的声像图特征是（）

下列属于条件致病菌的是

以下对老人膳食指导错误的是()

弱碱性药物在碱性尿液中()。

被誉为“地下运河”的我国古代著名水利工程的是()。

下列关于导游员接待儿童游客的做法中，正确的是()。

常用的WBS编码系统包括________。

Punditswhowanttosoundjudiciousarefondofwarningagainstgeneralizing.Eachcountryisdifferent,theysay,andnoonest