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

admin2021-01-13 98

问题在字符串的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函数值为_____________。

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

软考中级

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

阅读以下函数说明和Java代码，将应填入(n)处的字句写上。[说明]现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显示display()。需要新增图形Circle，又已知有

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

阅读以下说明，回答问题1～3，将解答填入对应的解答栏内。[说明]下图是有关学生(student)和学习(study)信息的对象关联图。

在文件系统中，下列关于当前目录(工作目录)的叙述中，不正确的是(22)。

在Word2010文档输入时，凡是已经显示在屏幕上的内容，都已保存在磁盘上。

关于虐待罪与虐待被监护、看护人罪的论述，下列哪些选项是正确的?()

1岁小儿正常的体格发育指标，以下哪项是错误的

淋巴结内的T淋巴细胞主要分布在

甲状腺功能减退症最具特征的临床表现是

产妇，贾某，24岁，于24小时前在当地医院经阴道分娩一女婴，诉呼吸困难，不能平卧，咳嗽、咯血，尿少，急来就诊。帮助确诊的辅助检查一般不包括

研究污染物在包气带和含水层中的物理、化学、生物作用规律，对()是非常有意义的。

通常，银行承担风险识别、风险计量、风险监测职责的部门是()。

A、Americansspendlessmoneyonpetsbecauseofthecurrenteconomicrecession.B、Americansspendlessmoneyonpetsinspiteof