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

admin2021-01-13 55

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

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

软考中级

根据【说明】中的描述，给出图6—4中A1和A2所对应的参与者。　　根据【说明】中的描述，给出图6—4中缺少的四个用例及其所对应的参与者。

阅读以下说明和c++代码，将应填入(n)处的字句写在答题纸对应栏内。[说明]很多时候，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下，Singleton模式有可能出现问题，需要进行

阅读以下说明和C代码，将应填入(n)处的字句写在对应栏内。[说明]函数combine(a，b，c)是计算两个整数的组合数。由于计算结果可能超出10ng整型的可表示范围，故采用数组方式存储，例如：k位长整数m用数组c[]存储结构如下：m=

阅读下列说明和E-R图，回答问题1至问题3，将解答填入对应栏内。[说明]某学校的教学系统描述如下：学生信息包括：学号(SNo)、姓名(Sname)、性别(Sex)、年龄(Age)、入学年份(Year)、主修专业(Major)，其

根据输差的计算公式：输差=[Q入-(Q出+Q存)]／Q入×100％可知，下列现象中引起输差为负的是()。

婴幼儿化脓性脑膜炎常见的病原茵是

白血病发生牙龈肿胀以哪一类型为最多见

区分心房和心室的标志是

关于格式条款的解释，下列说法中正确的是：()

按照银监会对个人理财业务的定义，商业银行为销售储蓄存款产品、信贷产品等进行的产品介绍和宣传不属于理财顾问服务。(　　)

Theideathatsomegroupsofpeoplemaybemoreintelligentthanothersisoneofthosehypothesesthatdarenotspeakitsname.

Thislistoflikelydonorsprovedtobeinvaluabletoourfund-raisingefforts.

In1923,______wasawardedtheNobelPrizeforliterature.

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

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

软考中级

根据【说明】中的描述，给出图6—4中A1和A2所对应的参与者。 根据【说明】中的描述，给出图6—4中缺少的四个用例及其所对应的参与者。

阅读以下说明和c++代码，将应填入(n)处的字句写在答题纸对应栏内。[说明]很多时候，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下，Singleton模式有可能出现问题，需要进行

阅读以下说明和C代码，将应填入(n)处的字句写在对应栏内。[说明]函数combine(a，b，c)是计算两个整数的组合数。由于计算结果可能超出10ng整型的可表示范围，故采用数组方式存储，例如：k位长整数m用数组c[]存储结构如下：m=

阅读下列说明和E-R图，回答问题1至问题3，将解答填入对应栏内。[说明]某学校的教学系统描述如下：学生信息包括：学号(SNo)、姓名(Sname)、性别(Sex)、年龄(Age)、入学年份(Year)、主修专业(Major)，其

根据输差的计算公式：输差=[Q入-(Q出+Q存)]／Q入×100％可知，下列现象中引起输差为负的是()。

婴幼儿化脓性脑膜炎常见的病原茵是

白血病发生牙龈肿胀以哪一类型为最多见

区分心房和心室的标志是

关于格式条款的解释，下列说法中正确的是：()

按照银监会对个人理财业务的定义，商业银行为销售储蓄存款产品、信贷产品等进行的产品介绍和宣传不属于理财顾问服务。( )

Theideathatsomegroupsofpeoplemaybemoreintelligentthanothersisoneofthosehypothesesthatdarenotspeakitsname.

Thislistoflikelydonorsprovedtobeinvaluabletoourfund-raisingefforts.

In1923,______wasawardedtheNobelPrizeforliterature.

　　根据【说明】中的描述，给出图6—4中A1和A2所对应的参与者。　　根据【说明】中的描述，给出图6—4中缺少的四个用例及其所对应的参与者。

按照银监会对个人理财业务的定义，商业银行为销售储蓄存款产品、信贷产品等进行的产品介绍和宣传不属于理财顾问服务。(　　)