已知字符串S为“abaabaabacacaabaabcc”,模式串t为“abaabc”。采用KMP算法进行匹配,第一次出现“失配”(s[i] ≠ 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
模式匹配(KMP)算法对普通的暴力匹配的改进在于:每当匹配过程中匹配失败时,主串(本题为S)的指针(i)不需要回溯,而是利用已经得到的“部分匹配”的结果将模式串(t)向右“滑动”尽可能远的一段距离后,继续进行比较。模式串“滑动”的距离是由模式串(t)本身决定的,即t的子串t[0…j-1]中前缀串和后缀串相等的最长长度。本题中第一次失配i=5,字串为“abaab”,其相等且最长的前后缀为“ab”,一次下一个j=2。
解答:
第一次出现&ldqu...
用户登录可进行刷题及查看答案
第一次出现“失配”(s[i] ≠ t[j])时,i = j = 5,隐藏含义是主串和模式串下标都从0开始,这个条件非常重要。
方法一:计算 next 数组后模拟
第一步:计算出模式串的next数组。
本人自编口诀优化前的next数组:第一格负一,第二格零,前缀等于后缀取最长。
这里由于主串和模式串下标都从0开始,没必要用优化后的next数组求解。优化后的next数组增加的1和下标都从0开始相比下标都从1开始减少的1正好相抵。
第二步:遍历主串对模式串进行匹配。
第一次匹配在模式串下标为5的位置出现失配,找到之前匹配的子串为abaab,最长相同前缀与后缀为ab,将前缀的ab移动到后缀ab的位置。
或者查表next数组失配字符c,其下标为5,其next值为next[5] = 2,已匹配字符数为5,移动位数 = 已匹配字符数 - 失配位置对应的匹配值 = 5 - 2 = 3。模式串向后移动3格,从失配位置开始重新进行匹配,此时 i = 5, j = 2。
或者查表next数组失配字符c,其下标为5,其next值为next[5] = 2,j指针直接跳转到模式串下标为2的位置,从失配位置开始重新进行匹配,此时 i = 5, j = 2。
本题选C。
方法三:贪心
贪心找到最多匹配的情况,同样画出上图。虽然这个方法不严谨,好在本题足够简单,从失配位置开始重新进行匹配,很容易看到i = 5, j = 2。
补充本人对本题完整KMP匹配过程的模拟。
登录后提交答案