设主串T=“abaabaabcabaabc”,模式串S=“abaabc”,采用KMP算法进行模式匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是
A. 9 B. 10 C. 12 D. 15
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
解:模式串 s = 'abaabc',最长相等前后缀长度有:
‘a',最长相等前后缀长度为 0
‘ab',最长相等前后缀长度为 0
‘aba',最长相等前后缀长度为 1
‘abaa',最长相等前后缀长度为 1
‘abaab',最长相等前后缀长度为 2
‘abaabc',最长相等前后缀长度为 0
所以,模式串 s = 'abaabc' 的部分匹配值 PM 为 001120
将 PM 右移一位,得 next 数组为 -1 0 0 1 1 2,即如下表:
【注意】如果串的位序是从 1 开始的,则 next 数组需要整体加1,若串的位序从 0 开始,则 next 数组不需要整体加 1。
第一趟连续比较 6 次,在模式串的 5 号位和主串的 5 号位匹配失败,模式串的下一个比较位置为 next[5] = 2,即下一次比较从模式串的 2 号位和主串的 5 号位开始,然后直到模式串 5 号位和主串8 号位匹配,第二趟比较 4 次,模式串匹配成功。
单个字符的比较次数为10次,因此选B。
不应该是9次吗?
快乐小土狗 回复 阿拉蕾上岸: 10次
本题选B。
解答:
方...
登录后提交答案