题目

KMP 算法使用修正后的 next 数组进行模式匹配，模式串 S = "aabaab"，当主串中某字符与 S 中某字符失去配对时，S 将向右滑动的最长距离是( )

错因

B

把 nextval 表算错了一项：在 j=5 处误判 P[5]='a' 与 P[next[5]]=P[2]='a' "不相等"，结果 nextval[5] 留成了 next[5]=2 而不是继续递归到 0，得 5−2=3 或干脆把 j=4/j=6 处的 4 当成最大值，没继续比到 j=5 的 5。漏检了 nextval 修正传播这一步。

C

完全没用"修正后的 next"，直接用了原始 next 数组：

j	1	2	3	4	5	6
next[j]	0	1	2	1	2	3
j − next[j]	1	1	1	3	3	3

得到最大滑动距离 = 3，但题目明确要求"修正后的 next 数组"——nextval 比 next 滑得更远，因为它把"用前缀重新匹配后还会立刻失配"那些无效尝试一并跳过。看错题干关键词。

D

按"模式串里最长重复前缀"目测：注意到 "aabaab" 里 "aab" 重复了一次，于是认为模式串只需要滑动到第二个 "aab" 的位置（滑 3 位）；又或者把"成功匹配整串后的下一次起点"当成"失配滑动距离"，把 m − 最长公共前后缀长度（6−4=2）当成答案。这个思路适用于"完全匹配后继续找下一次出现"，与失配时的滑动距离没有关系。

总解析

KMP "修正后的 next" 常指 nextval——即在 next 的基础上消除无效比较的优化版本。算这道题分三步。

Step 1：算原始 next（next[j] = 最长真前后缀公共长度 + 1）

j	1	2	3	4	5	6
P[j]	a	a	b	a	a	b
next[j]	0	1	2	1	2	3

Step 2：修正为 nextval（若 ，则 ；否则 ）

j	P[j]	next[j]	P[next[j]]	相等?	nextval[j]
1	a	0	—	—	0
2	a	1	a	✓	nextval[1] = 0
3	b	2	a	✗	2
4	a	1	a	✓	nextval[1] = 0
5	a	2	a	✓	nextval[2] = 0
6	b	3	b	✓	nextval[3] = 2

所以 nextval = [0, 0, 2, 0, 0, 2]。

Step 3：算每个 j 处的滑动距离 = j − nextval[j]

j	1	2	3	4	5	6
j − nextval[j]	1	2	1	4	5	4

最大滑动距离 = 5，发生在 j=5（即模式串第 5 个字符与主串失配时）。

直观理解为什么是 5：j=5 意味着已经成功匹配 "aaba"，第 5 位 P[5]='a' 失配。如果用普通 next，next[5]=2 会建议"从 P[2] 开始再比"，但 P[2]='a' 与刚才失配的主串字符还是 'a'——一定再次失配，浪费一次比较。nextval 把这种"注定会再失配"的尝试一并跳过，递归到 nextval[2]=0，等于让模式串整体从头开始匹配，相对主串滑了 5 位。

最终答案是 A（5）。