2. 考研
  3. 设主串T=“abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是( )。

设主串T=“abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是( )。

admin2020-06-17  75
问题 设主串T=“abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是(          )。
选项 A、9
B、10
C、12
D、15
答案B
解析 假设位序都是从0开始的，按照next数组生成算法，对于S有

根据KMP算法，第一趟连续对比6次，在模式串的5号位和主串的5号位匹配失败，模式串的下一个比较位置为next[5]，即下一次比较从模式串的2号位和主串5号位开始，然后直到模式串5号位和主串8号位匹配，第二趟比较4次，模式串匹配成功。单个字符的比较次数为10次，所以选B。
转载请注明原文地址:https://www.kaotiyun.com/show/OU3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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