在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式串的长度分别为n和m(且n远大于

admin2017-09-14 30

问题在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式串的长度分别为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+1趟的成功匹配也比较了m次。因此，在本题所述的匹配模式中，字符的比较次数最多为(n—m+1)×m次。

转载请注明原文地址:https://kaotiyun.com/show/o8RZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

客户/服务器模式产生于20世纪(27)上年代，它是基于(28)的要求而发展起来的。客户/服务器模式的第一个软件产品是(29)系统，客户/服务器模式通常在(30)环境下运行，客户端的软件具有(31)。

通信子网是由用作信息交换的节点计算机NC(Node　Computer)和通信线路组成的独立的通信系统，一般由OSI参考模型的(91)。

DNS服务器中的资源记录分成不同类型，其中指明区域主服务器和管理员邮件地址的是(51)，指明区域邮件服务器地址的是(52)。(52)

惩戒委员会应当集体作出决定，决定由出席会议委员的_____以上多数通过，并作出决定书。()

既能凉血止血，又能活血祛瘀的药物是既能化瘀止血，又能利尿通淋的药物是

根据《刑事诉讼法》及有关司法解释的规定，下列哪一项办案期限是不能重新计算的?()

下列费用中，应计入建筑安装工程材料费的有()。

关于营业税的营业额，下列表述正确的有(　　)。

冷凝器中冷却水温度降低时，其制冷剂的冷凝压力增大。()

尊重、爱护幼儿，严禁虐待、歧视、体罚和变相体罚、侮辱幼儿人格等损害幼儿()的行为。

你有一个同事负责开办一个培训班，但是他突然病倒了，领导把这件事交给你办，你准备怎么办?

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

软考中级

客户/服务器模式产生于20世纪(27)上年代，它是基于(28)的要求而发展起来的。客户/服务器模式的第一个软件产品是(29)系统，客户/服务器模式通常在(30)环境下运行，客户端的软件具有(31)。

通信子网是由用作信息交换的节点计算机NC(Node Computer)和通信线路组成的独立的通信系统，一般由OSI参考模型的(91)。

DNS服务器中的资源记录分成不同类型，其中指明区域主服务器和管理员邮件地址的是(51)，指明区域邮件服务器地址的是(52)。(52)

惩戒委员会应当集体作出决定，决定由出席会议委员的_____以上多数通过，并作出决定书。()

既能凉血止血，又能活血祛瘀的药物是既能化瘀止血，又能利尿通淋的药物是

根据《刑事诉讼法》及有关司法解释的规定，下列哪一项办案期限是不能重新计算的?()

下列费用中，应计入建筑安装工程材料费的有()。

关于营业税的营业额，下列表述正确的有( )。

冷凝器中冷却水温度降低时，其制冷剂的冷凝压力增大。()

尊重、爱护幼儿，严禁虐待、歧视、体罚和变相体罚、侮辱幼儿人格等损害幼儿()的行为。

你有一个同事负责开办一个培训班，但是他突然病倒了，领导把这件事交给你办，你准备怎么办?

通信子网是由用作信息交换的节点计算机NC(Node　Computer)和通信线路组成的独立的通信系统，一般由OSI参考模型的(91)。

关于营业税的营业额，下列表述正确的有(　　)。