2. 计算机
  3. (2012年下半年上午试题57)在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式

(2012年下半年上午试题57)在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式

admin2019-07-12  16
问题 (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://kaotiyun.com/show/D1CZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

相关试题推荐
随机试题
最新回复(0)