题目

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

错因

A

按朴素匹配的回退方式想：失配后把模式串整体右移一位，i 退回到本轮起点的下一位（i=1）、j 重置为 0 重新比。这正是 KMP 要避免的低效回退——朴素法之所以慢就是因为 i 会回退。KMP 的核心承诺是 i 永远不动，只动 j。

B

记得"i 不回退"，但误以为 j 总是重置为 0。这相当于把 next[5] 当成 0 用——退化成了"模式串整体后移到 i 处"，丢掉了已经匹配上的前缀信息。如果真把 j 设 0，就把 KMP 用成了和 A 等价的朴素法。next[5] 应是 2，不是 0。

D

next[5] = 2 算对了（j 退到 2 没错），但i 也跟着 +1 走到了 6。可能是把"失配后右移一位再继续"的朴素思维混进了 KMP，或把"j 退、i 进"两个动作叠加。KMP 的关键就是失配时 i 静止不动——只有匹配成功的字符才能让 i 前进。

总解析

KMP 的核心规则：

情况	i 的动作	j 的动作
匹配成功（s[i] = t[j]）	i++	j++
失配（s[i] ≠ t[j]）	不动	j = next[j]
失配且 j = 0 已是开头	i++	j 仍为 0

失配时 i 不回退，是 KMP 比朴素匹配快的根本原因。

计算 t = "abaabc" 的 next 数组（0-indexed，约定 next[j] = "t[0..j-1] 的最长真前缀 = 真后缀"的长度，next[0] 不参与回退）：

j	t[j]	t[0..j-1]	最长 真前缀=真后缀 长度	next[j]
0	a	""	—	—
1	b	"a"	0	0
2	a	"ab"	0	0
3	a	"aba"	"a" 长 1	1
4	b	"abaa"	"a" 长 1	1
5	c	"abaab"	"ab" 长 2	2

"abaab" 的真前缀有 "a", "ab", "aba", "abaa"；真后缀有 "b", "ab", "aab", "baab"。共同的最长是 "ab"，长度 2。所以 next[5] = 2。

应用 KMP 失配规则：

题目给出 i = j = 5 时失配（s[5]='a' ≠ t[5]='c'）。

• i：保持 5 不变
• j：j ← next[5] = 2

直观图示——模式串向右滑动到 "ab" 与 s 中已匹配的 "ab"（即 s[3..4]）对齐，从 t[2] 开始与 s[5] 继续比：

位置:   0 1 2 3 4 5 6 7 ...
s:      a b a a b a a b ...
t (旧):  a b a a b c              ← 旧位置
t (新):        a b a a b c        ← 滑动到此处，从 j=2 开始
                   ↑
              i=5 不动，j=2 接着比

下一次比较的是 s[5]='a' 和 t[2]='a' → 匹配，继续 i++、j++。

为什么 j 退到 2 是对的：已经匹配上的 "abaab"（s[0..4] = t[0..4]）后缀里有 "ab" 等于 t 的前缀 "ab"——意味着我们不需要再比较 s[3..4]，可以直接把 t 的 "ab" 对齐到这里，从 t[2] 接着往下比。

送命陷阱：把 KMP 的"j ← next[j]"误记为"j ← 0"或者"i ← i+1"。口诀：失配时 i 不动，j 退到 next[j]。

最终答案是 C（i = 5, j = 2）。