题目
KMP算法[1]使用修正后的next数组进行模式匹配[2],模式串S= "aabaab",当主串中某字符与S中某字符失配时,S将向右滑动的最长距离是A.5B.4 C.3 D.2
KMP算法[1]使用修正后的next数组进行模式匹配[2],模式串S= "aabaab",当主串中某字符与S中某字符失配时,S将向右滑动的最长距离是
A.5
B.4
C.3
D.2
题目解答
答案
首先，我们需要计算修正后的next数组。对于模式串S中的每个字符，next数组记录的是在该字符失配时，模式串向右滑动的最长距离。
根据KMP算法修正next数组的规则，对于字符S[i]，若失配，我们将模式串向右滑动的距离为next[i]。
通过计算可得到修正后的next数组为[0, 1, 0, 1, 2, 3]。
接下来，我们需要找到主串中某字符与S中某字符失配时，S需要向右滑动的最长距离。当某字符与S中的字符失配时，我们可以根据修正后的next数组来确定滑动的距离。
在这个例子中，主串中某字符与S中某字符失配时，S需要向右滑动的最长距离为next[5]。
因此，最长距离为3。
----
所以，正确答案是C选项：3
解析
KMP算法的核心在于通过预处理模式串生成修正后的next数组，用于记录在失配时模式串向右滑动的最大距离。本题的关键在于：
- 正确计算next数组：根据模式串的前缀与后缀匹配规则，逐个位置推导。
- 理解next数组的意义：当匹配到模式串第$i$个字符时失配，模式串会向右移动
next[i]位。 - 寻找最大值：题目要求“最长滑动距离”，即找出next数组中的最大值。
计算修正后的next数组
模式串$S = "aabaab"$，长度为6。按KMP算法规则计算：
- 初始化：
next[0] = 0（第一个字符无前缀）。 - 逐个位置计算：
- i=1：比较$S[1] = 'a'$与前缀末尾$S[0] = 'a'$，匹配，
next[1] = 1。 - i=2：前缀长度为1，比较$S[2] = 'b'$与$S[1] = 'a'$不匹配，回溯后
next[2] = 0。 - i=3：前缀长度为0，比较$S[3] = 'a'$与$S[0] = 'a'$匹配，
next[3] = 1。 - i=4：前缀长度为1，比较$S[4] = 'a'$与$S[1] = 'a'$匹配，
next[4] = 2。 - i=5：前缀长度为2，比较$S[5] = 'b'$与$S[2] = 'b'$匹配，
next[5] = 3。
- i=1：比较$S[1] = 'a'$与前缀末尾$S[0] = 'a'$，匹配，
最终得到next = [0, 1, 0, 1, 2, 3]。
确定最长滑动距离
next数组中的最大值为3，对应选项C。