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

admin2021-01-13 62

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

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

软考中级

把上面用关系表示的实体，实体与实体之间的联系，用E-R图表示出来，要求在图中表示联系的类型(1:1，L:N，M:N)。使用关系代数表达式写出查询所有年龄在20岁以下的学生姓名和年龄。

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

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

回归分析法

当全球一体化的压力高、当地反应化的压力低时，跨国企业将采取的竞争战略是（）

计算D：x2+y2≤2x．

能治疗慢性肾炎、红斑狼疮的祛风湿药是(　　)

牵正散的功用是()

患者，女，30岁，症见寒热如疟，寒轻热重，口苦胸闷，吐酸苦水或呕黄涎而黏，甚则干呕呃逆，胸胁胀痛，舌红苔白脉数而右滑左弦者。治宜选用

创造性的基本特征是流畅性、变通性、独创性。()

(2017年真题)秦简《法律答问》记载：“甲小未盈六尺，有马一匹自牧之，今马为人败，食人稼一石，问当论不当?不当论及偿稼。”依照该解答，秦律判断责任能力的标准是()。

Accordingtoanewschoolofscientists,technologyhasbeenoverlookedasaforceinexpandingthehorizonsofscientificknowl

Thereisonepartofwomen’smagazinesthateverymanreads.Itisthesectionpopularlyknownasthe"agonycolumns",wherewom

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

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

软考中级

把上面用关系表示的实体，实体与实体之间的联系，用E-R图表示出来，要求在图中表示联系的类型(1:1，L:N，M:N)。使用关系代数表达式写出查询所有年龄在20岁以下的学生姓名和年龄。

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

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

回归分析法

当全球一体化的压力高、当地反应化的压力低时，跨国企业将采取的竞争战略是（）

计算D：x2+y2≤2x．

能治疗慢性肾炎、红斑狼疮的祛风湿药是( )

牵正散的功用是()

患者，女，30岁，症见寒热如疟，寒轻热重，口苦胸闷，吐酸苦水或呕黄涎而黏，甚则干呕呃逆，胸胁胀痛，舌红苔白脉数而右滑左弦者。治宜选用

创造性的基本特征是流畅性、变通性、独创性。()

(2017年真题)秦简《法律答问》记载：“甲小未盈六尺，有马一匹自牧之，今马为人败，食人稼一石，问当论不当?不当论及偿稼。”依照该解答，秦律判断责任能力的标准是()。

Accordingtoanewschoolofscientists,technologyhasbeenoverlookedasaforceinexpandingthehorizonsofscientificknowl

Thereisonepartofwomen’smagazinesthateverymanreads.Itisthesectionpopularlyknownasthe"agonycolumns",wherewom

能治疗慢性肾炎、红斑狼疮的祛风湿药是(　　)