题目

设主串 T="abaabaabcabaabc"，模式串 S="abaabc"，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是( )。

错因

A

漏算了"失配"那一次比较。匹配跟踪时只把成功匹配的字符比较计数，把 那次"失败"看成 j 直接跳转、不算字符比较，于是少了 1 次得到 9。但失配的字符比较本身是真实发生的字符比较，必须计入。

C

把 j 回退动作也错算成额外的字符比较。例如认为 从 5 回退到 2 的过程中"重新对齐"会涉及多个字符比较，结果多算 2 次。其实 是查表跳转，不进行字符比较，回退后才在新位置进行 1 次新比较。

D

完全按朴素模式匹配（BF 算法）的方式计算：每次失配把主串指针 i 也回退到 i−j+1 起点重新匹配，整体比较次数接近 的量级。但题目明说用 KMP，KMP 的核心优势就是主串指针 i 永不回退，比较次数远少于 BF。

总解析

步骤 1：求模式串 S = "abaabc" 的 next 数组（next[j] = S[0..j−1] 的最长真前缀=真后缀长度）

j	S[0..j−1]	最长前后缀公共长度	next[j]
0	""	0	0
1	"a"	0	0
2	"ab"	0	0
3	"aba"	"a"="a"，长度 1	1
4	"abaa"	"a"="a"，长度 1	1
5	"abaab"	"ab"="ab"，长度 2	2

步骤 2：跟踪匹配过程（i 是主串指针，j 是模式指针；每次" vs "算 1 次比较）

步	i	j	T[i]	S[j]	结果	累计比较
1	0	0	a	a	匹配 → i++, j++	1
2	1	1	b	b	匹配	2
3	2	2	a	a	匹配	3
4	3	3	a	a	匹配	4
5	4	4	b	b	匹配	5
6	5	5	a	c	失配 → j=next[5]=2，i 不动	6
7	5	2	a	a	匹配	7
8	6	3	a	a	匹配	8
9	7	4	b	b	匹配	9
10	8	5	c	c	匹配 → j+1=6=|S|，匹配成功	10

关键观察：

• 第 6 步是失配但仍算 1 次比较（"=a vs =c"是一次真实的字符比较，不能因为结果是"不等"就漏算）。
• 从 5 回退到 2 是查 next 表的跳转，不进行字符比较。
• 之后第 7 步是 与 的全新比较——主串位置没动，但模式位置变了，是新的 1 次。

总比较次数 = 10。最终答案是 B。