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

admin2021-01-13 31

问题 (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://jikaoti.com/ti/SKG7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

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

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]现有如下关系模式：R(A#，B#，C，DE)，其中，A#，B#为组合键，R上存在的函数依赖有(A#，B#)→E，B#→C，C→D

阅读以下算法说明和C程序，根据要求回答问题1至问题2。[说明][算法4-1]的功能是：用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如图4-18所示。在[算法4-1

请仔细阅读以下关于某传输系统的技术说明、状态转换图及Java程序，根据要求回答问题1～问题2。[说明]传输门是传输系统中的重要装置。传输门具有Open(打开)、Closed(关闭)、Opening(正在打开)、StayOpen(保持打开)

根据【说明】，将图6—1中的E1一E3填充完整。　　图6—1中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。(注：数据流的起点和终点均采用图中的符号和描述)

二极管两端的电压与电流的关系称为二极管的伏安特性。（）

在《寡人之于国也》中，孟子认为造成“颁白者不负戴于道路”良好社会风尚的主要措施是

交感神经系统兴奋时，引起

砂浆的和易性好坏主要取决于砂浆的()。

绿色贸易壁垒的主要内容包括()。

“进口口岸”栏应填()。“提运单号”栏应填()。

被称为“现代教育学之父”的是()。

根据操作数所在的位置，指出其寻址方式。操作数在寄存器中：(14)；操作数地址在寄存器中：(15)；操作数在指令中：(16)；操作数地址在指令中：(17)。

在Windows98中，msdos.sys是一个十分重要的系统配置文件，通过对其修改(例如修改BootMulti、BootGUI、BootMenu等命令)可以改变Windows98的启动方式。如果要使Windows98启动时直接进入到DOS状态，该文

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

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

软考中级

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

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]现有如下关系模式：R(A#，B#，C，DE)，其中，A#，B#为组合键，R上存在的函数依赖有(A#，B#)→E，B#→C，C→D

阅读以下算法说明和C程序，根据要求回答问题1至问题2。[说明][算法4-1]的功能是：用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如图4-18所示。在[算法4-1

请仔细阅读以下关于某传输系统的技术说明、状态转换图及Java程序，根据要求回答问题1～问题2。[说明]传输门是传输系统中的重要装置。传输门具有Open(打开)、Closed(关闭)、Opening(正在打开)、StayOpen(保持打开)

根据【说明】，将图6—1中的E1一E3填充完整。 图6—1中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。(注：数据流的起点和终点均采用图中的符号和描述)

二极管两端的电压与电流的关系称为二极管的伏安特性。（）

在《寡人之于国也》中，孟子认为造成“颁白者不负戴于道路”良好社会风尚的主要措施是

交感神经系统兴奋时，引起

砂浆的和易性好坏主要取决于砂浆的()。

绿色贸易壁垒的主要内容包括()。

“进口口岸”栏应填()。“提运单号”栏应填()。

被称为“现代教育学之父”的是()。

根据操作数所在的位置，指出其寻址方式。操作数在寄存器中：(14)；操作数地址在寄存器中：(15)；操作数在指令中：(16)；操作数地址在指令中：(17)。

在Windows98中，msdos.sys是一个十分重要的系统配置文件，通过对其修改(例如修改BootMulti、BootGUI、BootMenu等命令)可以改变Windows98的启动方式。如果要使Windows98启动时直接进入到DOS状态，该文

　　根据【说明】，将图6—1中的E1一E3填充完整。　　图6—1中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。(注：数据流的起点和终点均采用图中的符号和描述)