首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年下半年上午试题57)在字符串的模式匹配过程中,如果模式串的每个字符依次和主串中的一个连续的字符序列相等,则称为匹配成功。如果不能在主串中找到与模式串相同的子串,则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中,若主串和模式
(2012年下半年上午试题57)在字符串的模式匹配过程中,如果模式串的每个字符依次和主串中的一个连续的字符序列相等,则称为匹配成功。如果不能在主串中找到与模式串相同的子串,则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中,若主串和模式
admin
2019-07-12
10
问题
(2012年下半年上午试题57)在字符串的模式匹配过程中,如果模式串的每个字符依次和主串中的一个连续的字符序列相等,则称为匹配成功。如果不能在主串中找到与模式串相同的子串,则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中,若主串和模式串的长度分别为n和m(且n远大于m),且恰好在主串末尾的n个字符处匹配成功,则在上述的模式匹配过程中,字符的比较次数最多为______。
选项
A、n×m
B、(n-m+1)×m
C、(n-m-1)×m
D、(n-m)×n
答案
B
解析
在最坏情况下,每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等,则主串中新一趟的起始位置为i-m+2。若从主串的第i个字符开始匹配时成功,则前i趟不成功的匹配中,每趟都比较了m次,总共比较了i×m次,第i+l趟的成功匹配也比较了m次。因此,在本题所述的匹配模式中,字符的比较次数最多为(n-m+1)×m次。
转载请注明原文地址:https://jikaoti.com/ti/iqG7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
以太网的数据帧封装如下图所示,包含在IP数据报中的数据部分最长应该是(23)________________字节。
网络拓扑设计对网络的影响主要表现在__________。(2013年上半年试题)①网络性能②系统可靠性③出口带宽④网络协议
阅读以下说明和VisualBasic代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape,现有三个类CPoint、CLine和CCircle,它们都具有IShape界面。相应的类图关系如图7-1所示。
阅读以下说明和Java代码,将应填入(n)处。[说明]在一公文处理系统中,开发者定义了一个公文类OfficeDoc,其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时,关注此OfficeDoc类对象的相应的DocExplo
阅读以下说明和C++代码,将应填入(n)处。[说明]在一公文处理系统中,开发者定义了一个公文类OfficeDoc,其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时,关注此OfficeDoc类对象的相应的DocExplor
请用120字以内文字,从业务的继承性、升级成本(时间、工作量)和扩展性三个方面简要说明开发人员所提方案的优点。WebService的三个基本技术是WSDL、SOAP、UDDI,它们都是以XML为基础定义的。请用120字以内文字,简要说明WSDL、SO
阅读以下说明和C++代码。【说明】传输门是传输系统中的重要装置。传输门具有Open(打开)、Closed(关闭)、Opening(正在打开)、StayOpen(保持打开)和Closing(正在关闭)五种状态。触发传输门状态转换的事件有click
己知某类库开发商提供了一套类库,类库中定义了Application类和Document类,它们之间的关系如图16—5所示。其中,Application类表示应用程序自身,而Document类则表示应用程序打开的文档。Application类负责打开一个已有
设计高质量的软件是软件设计追求的一个重要目标。可移植性、可维护性、可靠性、效率、可理解性和可使用性等都是评价软件质量的重要方面。可移植性反映出把一个原先在某种硬件或软件环境下正常运行的软件移植到另—个硬件或软件环境下,使该软件也能正确地运行的难易程度。为了
甲公司从市场上购买丙公司生产的部件Q,作为生产甲公司产品的部件。乙公司已经取得部件Q的中国发明权,并许可丙公司生产销售该部件Q。甲公司的行为(10)。
随机试题
A.食物中缺碘B.食物中缺钙C.幼年时生长素不足D.糖皮质激素分泌增加E.幼年时甲状腺机能不足
A.干化学法检测尿糖时出现假阳性B.班氏法检测尿糖出现假阴性C.磺基水杨酸法检测蛋白出现假阴性D.干化学法检测蛋白出现假阴性E.干化学法检测亚硝酸盐出现假阴性大剂量青霉素可产生的影响是
关于粗率和标准化率的意义,下列哪一项是正确的
腹部闭合损伤时,最常受到损伤的空腔脏器是()
某市国有公司与某个外资企业共同创办了一家娱乐城,甲被国有公司委派到其中担任副总经理,主管财务。职工乙见到甲受到监督的机会很少,就说一起侵占单位资金,乙利用自己工作机会制作虚假的发票和收据,让甲进行报销。两人侵吞了6万多元,乙分得4万元。接着,乙利用自己报账
合同管理制要求各类合同均要有()。
在学校社会工作中,以下哪些是小组工作的组织原则?()。
从罗特控制点的理论看,主张“谋事在人成事在天”的人们归因倾向属于()。(2004年6月三级真题)
设求y(n)(0).
(2013年上半年)公司承接了一个信息系统开发项目,按照能力成熟度模型CMMI制定了软件开发的流程与规范,委派小赵为这个项目的项目经理。小赵具有3年的软件项目开发与管理经验。公司认为这个项目的技术难度比较低,把两个月前刚从大学招聘来的9个计算机科
最新回复
(
0
)