首页
登录
从业资格
在字符串的KMP模式匹配锋法中,需要求解模式串p的next函数值,其定义如下所示
在字符串的KMP模式匹配锋法中,需要求解模式串p的next函数值,其定义如下所示
题库
2022-08-02
70
问题
在字符串的KMP模式匹配锋法中,需要求解模式串p的next函数值,其定义如下所示。若模式串p为“aaabaaa”,则其next函数值为( )。
A.0123123B.0123210C.0123432D.0123456
选项
A.0123123
B.0123210
C.0123432
D.0123456
答案
A
解析
KMP模式匹配算法通俗点说就是一种在一个字符串中定位另一个串的高效算法。其实我们在做这个题目时,也可以不需要知道KMP模式匹配算法,可以根据题目给出的定义式来求解。
【对于本题公式】
1、当j=1时,由(1)式,next[1]=0;
2、当j!=1时,由(2)式,max{k|1<k<j'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'},即选择符合要求的最大k值,要求:1<k<j,并且满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1',如果有满足要求的k值,则next[j]=max{k};如果找不到满足条件的k值,则由(3)式next[j]=1。
3、取值范围,j、k都为正整数,且1<=j<=5
【求取next[]过程如下】
1、当j=1时,由(1)式,next[1]=0;
2、当j=2时,找不到满足1<k<j的数k,由(3)式,next[2]=1;
3、当j=3时,满足1<k<j的数k=2,同时需要满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。'p1p2...pk-1'='p1p2...p1'=p1,为第一个字母a;'pj-k+1pj-k+2...pj-1'='p2p3...p2'=p2,为第二个字母a,此时,k满足条件,由(2)式,next[3]=k=2。
4、当j=4时,满足1<k<j的数k=2或3:
(1)当k=2,'p1p2...pk-1'='p1p2...p1'=p1,为第一个字母a,'p1p2...pk-1'='p3p4...p3'=p3,为第三个字母a,满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
(2)当k=3,'p1p2...pk-1'='p1p2...p2'=p1p2,为第一二字母aa,'pj-k+1pj-k+2...pj-1'='p2p3...p3'=p2p3,为第二三个字母aa,'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
因此next[4]=max{2,3}=3。
5、j=5,满足1<k<j的数k=2、3或4:
(1)当k=2,'p1p2...pk-1'='p1p2...p1'=p1,为第一个字母a,'p1p2...pj-1'='p4p5...p4'=p4,为第四个字母b,不满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
(2)当k=3,'p1p2...pk-1'='p1p2...p2'=p1p2,为第一二字母aa,'pj-k+1pj-k+2...pj-1'='p3p4...p4'=p3p4,为第三四个字母ab,不满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
(3)当k=4,'p1p2...pk-1'='p1p2Lp3'=p1p2p3,为第一二三字母aaa,'pj-k+1pj-k+2...pj-1'='p2p3...p4'=p2p3p4,为第二三四个字母aab,不满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
因此,当j=5时,没有满足条件k,此时由(3)式,next[5]=1。
同理我们可以求得当j=6,j=7的结果,本题正确答案选A。
转载请注明原文地址:https://tihaiku.com/congyezige/2410288.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
企业信息化建设需要大量的资金投入,成本支出项目多且数额大。在企业信息化建设成本支
为了真正了解各业务部门的IT服务需求,并为其提供令人满意的IT服务,企业需要进行
IT服务级别管理是定义、协商、订约、检测和评审提供给客户服务的质量水准的流程。它
某公司员工赵忻是一名软件设计师,按公司规定编写软件文档需要上交公司存档。这些软件
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,链接顶点的边表示包含的活动
企业信息资源管理不是把资源整合起来就行了,而是需要一个有效的信息资源管理体系,其
()要求关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。A.1NF
数据的逻辑独立性由()的映射实现。A.外模式到逻辑模式 B.外模式到内模式
关系模式R(U,F)中,属性集U={A,B,C,D,E},函数依赖集F=(A→B
随机试题
以()为代表的期货投资基金的监管模式,是通过一些间接的法规来制约基金业的活动,并没有全国性管理机构,主要依靠证券交易所、基金业协会等进行自我监管。A、
[originaltext]W:John,haveyouchosenaphysicaleducationclassyetforthis
试述结肠癌的诊断要点。
柯萨奇病毒A组引起的疾病不正确的是A.手足口病B.疱疹性咽峡炎C.流行性胸痛D.
Thechangeinthatvillagewasmiraculou
清理呼吸道无效的相关因素不包括A.不恰当的体位 B.疲乏无力 C.严重水肿
双母并列运行时,倒母线操作的正确顺序是()。投入母线保护互联压板→拉开母联断路器
数学学习中由数字运算到字母运算的转化,属于( )A.自上而下的迁移 B.自下
收入总量调控政策通过()来实施。A:财政机制B:市场机制C:行政干预D:货
关于项目进度计划及其优化的说法,正确的有()。A.计划中的关键工作指的是自由时
最新回复
(
0
)