4.2.3 KMP 优化：避免回退后立刻比较同一个失败字符

某些教材用 1 基 next，并进一步构造 nextval。优化动机是：若失配位置字符与回退后将比较的模式字符相同，那么这次比较已知仍会失败，可以继续沿失败链接回退。0 基前缀函数实现中，也可在自动机或失配表构造时压缩这类重复边。

设模式中一段重复字符 aaaaab。朴素失败链接可能让 j 逐级经历多个表示相同 a 的状态；优化表把这些必败状态跳过。它减少比较次数的常数，但不改变 KMP 的 $O(n+m)$ 渐近复杂度。

必须先得到正确的基础失败表，再做优化。以 1 基思想描述：若 P[j] == P[next[j]]，令 nextval[j]=nextval[next[j]]；否则 nextval[j]=next[j]。不同教材对 next[1] 取 0 或 -1、数组是否从 0 开始各有约定，考试时应根据给定定义现场推导。

手工推演的可靠方法是画“状态 j 表示已经匹配多少字符”。失败边必须指向严格更短且能与已匹配后缀对齐的前缀状态；优化只能跨过下一次必然比较同一字符的状态，不能跳过可能成功的状态。

工程中还可把模式预处理成有限状态转移表，扫描每个主串字符时直接查下一状态。若字符集大小为 $|\Sigma |$，完整表空间可能为 $O(m|\Sigma |)$，以空间换更简单的常数时间转移。

错解反馈：认为优化后复杂度从 $O(nm)$ 才变为 $O(n)$，混淆基础 KMP 与朴素算法；机械套 nextval 而不看下标约定；为了少比较而跳过可能匹配状态，都会破坏正确性。

迁移题：模式含长重复前缀时，基础 KMP 和优化版谁的渐近复杂度更好？答案相同，都是线性；优化仅减少部分必败比较。独立验收：能对给定失败状态解释“为何这个回退安全”，而不是只报数组数字。