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

admin2021-01-13 73

问题在字符串的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)处的字句写上。[说明]现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显不display()。需要新增图形Circle，又已知有类XX

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

阅读下列说明Java代码，将应填入(1)～(6)处的字句写在答题纸的对应栏内。【说明】现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQILServer和Access两种数据库以及系统中的数

UML的词汇表包含以下3种构造模块，(16)是对模型中最具有代表性成分的抽象，(17)把(16)结合在一起，(18)聚集了相关的(16)。

A、颊肌B、咬肌C、颏舌肌D、下颁舌骨肌E、胸锁乳突肌舌下神经支配

狂犬病的健康教育内容有（）

糖尿病酮症酸中毒时脑水肿的原因可能为

麻疹的预防措施不包括

若矩阵的秩为2，则α=()。

各单位应当定期将会计账簿记录与相应的会计凭证记录逐项核对，检查()是否一致。

中国2001年发行的中国人世成功纪念邮票(已经使用)

人民警察的内务纪律涉及人民警察的()方面。

设f(x)可导，F(x)=f(x)(1+|sinx|)，则f(0)=0是F(x)在x=0处可导的()

请简述单元测试的内容。集成测试也叫组装测试或者联合测试，请简要叙述组装测试时需要注意的问题。