在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为_____________。

admin2021-01-13 78

问题在字符串的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；是取较大值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/iXCZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为_____________。

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

软考中级

阅读下列说明和c++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】现欲实现一个图像浏览系统，要求该系统能够显示BMP、JPEG和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG

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

分析车辆的状态和事件，指出图1中的(1)、(2)、(3)、(4)分别是什么?分析用户的状态和事件，指出图2中的(5)、(6)、(7)、(8)分别是什么?(注意，用户与车辆在状态图中的关系)。

在指令系统的各种寻址方式中，获取操作数最快的方式是(1)。若操作数的地址包含在指令中，则属于(2)方式。

连结脊柱的主要韧带有_______、_、_、_、_和_______。因韧带含水量较少，在T1WI和T2WI上均呈

设D是曲线y=x2与y=1所围闭区域，等于()。

下列关于信贷授权形式的划分，正确的有()。

行书源于哪位书法家()

2016年2月，中共中央办公厅印发通知，要求在全党开展“两学一做”学习教育。“两学一做”具体是指学党章、学党规、做合格党员。()

【中统】

Individualsareincreasinglybeingaskedtotakeonsoleresponsibility—andassumetheburdenofrisk—forcomplexsavingstasks

Traditionalsuperstitionsandbeliefs【C1】disappearaltogether;theyassumenewformsand【C2】tocontemporarycond

A、$15775.B、$16000.C、$16075.D、$13775.C

在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为_____________。

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

软考中级

阅读下列说明和c++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】现欲实现一个图像浏览系统，要求该系统能够显示BMP、JPEG和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG

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

分析车辆的状态和事件，指出图1中的(1)、(2)、(3)、(4)分别是什么?分析用户的状态和事件，指出图2中的(5)、(6)、(7)、(8)分别是什么?(注意，用户与车辆在状态图中的关系)。

在指令系统的各种寻址方式中，获取操作数最快的方式是(1)。若操作数的地址包含在指令中，则属于(2)方式。

连结脊柱的主要韧带有_______________、_______________、_______________、_______________、_______________和_______________。因韧带含水量较少，在T1WI和T2WI上均呈

设D是曲线y=x2与y=1所围闭区域，等于()。

下列关于信贷授权形式的划分，正确的有()。

行书源于哪位书法家()

2016年2月，中共中央办公厅印发通知，要求在全党开展“两学一做”学习教育。“两学一做”具体是指学党章、学党规、做合格党员。()

【中统】

Individualsareincreasinglybeingaskedtotakeonsoleresponsibility—andassumetheburdenofrisk—forcomplexsavingstasks

Traditionalsuperstitionsandbeliefs【C1】______disappearaltogether;theyassumenewformsand【C2】______tocontemporarycond

A、$15775.B、$16000.C、$16075.D、$13775.C

连结脊柱的主要韧带有_______、_、_、_、_和_______。因韧带含水量较少，在T1WI和T2WI上均呈

Traditionalsuperstitionsandbeliefs【C1】disappearaltogether;theyassumenewformsand【C2】tocontemporarycond