首页
登录
从业资格
在字符串的模式匹配过程中,如果模式串的每个字符依次和主事中一个连续的字符序列相等
在字符串的模式匹配过程中,如果模式串的每个字符依次和主事中一个连续的字符序列相等
练习题库
2022-08-02
95
问题
在字符串的模式匹配过程中,如果模式串的每个字符依次和主事中一个连续的字符序列相等,则称为匹配成功。如果不能在主串中找到与模式串相同的子串,则称为匹配失败。在布鲁特—福斯模式匹配算法(朴素的或基本的模式匹配)中,若主串和模式串的长度分别为n和m(且n远大于m),且恰好在主串末尾的m个字符处匹配成功,则在上述的模式匹配过程中,字符的比较次数最多为( )。A.n*mB.(n-m+1)*mC.(n-m-1)*mD.(n-m)*n
选项
A.n*m
B.(n-m+1)*m
C.(n-m-1)*m
D.(n-m)*n
答案
B
解析
本题主要考查字符串的匹配。在本题的描述中,告诉我们是在主串末尾的m个字符处匹配成功,那么在这之前,从左到右依次匹配了n-m次,且都失败了,最坏的情况,就是每次匹配都是匹配到最后一个字符不符合,因此每次匹配的比较次数就是子串的长度,即m。而匹配成功时,一共也比较了m次。所以字符的比较次数最多为(n-m+1)*m次。
转载请注明原文地址:https://tihaiku.com/congyezige/2410083.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
CPU的速度要远快于打印机的速度,为解决这个速度不匹配的问题,可以使用()
某企业网上书城系统的部分关系模式如下: 书籍信息表:books(bookn
某竞赛管理系统的部分数据库关系模式如下: 选手:PLAYER(PnOPha
关系模式R<{A,B,C},{AC→B,B→C}>的候选码之一是( );由于该
令序列X、Y、Z的每个元素都按顺序进栈,且每个元素进栈和出栈仅一次。则不可能得到
浏览器开启了无痕浏览模式后,( )依然会被保存下来。A.浏览历史 B.搜索历
某汽车租赁公司建立汽车租赁管理系统,其数据库的部分关系模式如下: 用户:US
给定关系模式R<U,F>,U={A,B,C,D,E},F={B→A,D→A,A→
给定关系模式R<U,F>,其中U为关系R的属性集,F是U上的一组函数依赖,X、Y
设关系模式R<U,F>,其中U为属性集,F是U上的一组函数依赖,那么Armstr
随机试题
EarlyinthemorningMr.Smithiscuttingthegrassintheyard.Mr.Greenc
(Would)youmind(waiting)amomentforme?Myworkwillbe(finished)(atnoti
PresidentHoover’sPoliticsDuringtheGreatDepressionAtfirst
IamquitesurethatIcan________Michaelintolettingususehiscartomorrow
InAmerica,thetraditionaltimeforgraduationsis[br][originaltext]InA
Moreoftenthannot,itisdifficultto______theexactmeaningofaChineseidio
Wemightbelivingforlongerthanever,butwearesick.About95percento
[originaltext]Iwouldlikeparticularlytotalkabouttheneedtodevelopa
下面关于单链结合蛋白(SSB)的描述哪个是不正确的?A.与单链DNA结合,防止碱
下列四个选项中,()不能构成一个产业。A:建筑业B:服务业C:国家机关D:
最新回复
(
0
)