2. 考研
  3. 已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i-j=5，则下次开始匹配时，i和j的值分别是_______。

已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i-j=5，则下次开始匹配时，i和j的值分别是_______。

admin2015-12-30  76
问题 已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s≠t[j])时，i-j=5，则下次开始匹配时，i和j的值分别是_______。
选项 A、i=1，j=0
B、i=5，j=0
C、i=5，j=2
D、i=6，j=2
答案C
解析 由题中“失配s≠t[j]时，i=j=5”，可知题中的主串和模式串的位序都是从0开始的(要注意灵活应变)。按照next数组生成算法，对于t有：

依据KMP算法“当失配时，i不变，j回退到next[j]的位置并重新比较”，当失配s≠t[j]时，i=j=5，由上表不难得出next[j]=next[5]=2(位序从O开始)。从而最后结果应为：i=5(i保持不变)，j=2。
转载请注明原文地址:https://kaotiyun.com/show/fzRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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