4.2 选择题讲评：前后缀、下标约定与复杂度

KMP 选择题最常见的陷阱是把真前缀、真后缀和子串混为一谈。真前缀必须从首字符开始且不能等于整个串；真后缀必须到末字符结束。ababa 的相等最长真前后缀是 aba，长度 3，而中间的 bab 不是前缀。

多选：关于 KMP，正确的是 A 主串指针无需回退；B 预处理与模式有关而与主串无关；C 最坏时间 $O(n+m)$；D 任意失配都把模式下标清零。答案 A、B、C。D 丢弃了可复用前后缀。

计算题：模式 ababaca 的前缀函数是 [0,0,1,2,3,0,1]。求某位时可从前一位候选长度开始，若字符不同便沿前缀表继续缩短，直到相同或归零。不能把上一位简单加一。

朴素算法在最佳情形可能接近 $O(n)$，例如每个起点首字符即失败；但最坏为 $O(nm)$。KMP 的优势是保证最坏线性，并非所有短文本上都一定更快，预处理也有成本。

若题目给的是 1 基 next 而不是 0 基 pi，先写定义再计算。不同定义下数字可以不同，但表达的失败后对齐关系一致。答案与教材表不同不一定是算法错，可能只是约定不同；考试必须服从题设。

匹配次数题还要区分字符比较次数与主循环轮数。同一个主串字符可能在若干失败状态下与不同模式字符比较，但失败链接严格缩短状态，整个扫描的比较总量仍受线性界控制，不能把局部多次比较直接乘成 $nm$。

错解反馈：把最长公共前后缀理解为任意重复子串；认为 KMP 不发生模式回退；看到双层循环就判 $O(nm)$；不检查数组起点直接比较答案，都会误判。

迁移题（多选）：模式预处理表发生变化的因素有哪些？A 模式字符 B 主串长度 C 下标与表定义 D 字符比较规则。答案 A、C、D；同一模式的表不依赖具体主串长度。验收要求为每个选项给依据。