KMP算法：再改进
看懂next数组为何仍会浪费比较，掌握nextval的推导与边界细节
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
KMP算法：再改进
看懂next数组为何仍会浪费比较，掌握nextval的推导与边界细节
美中不足：next的盲点
上一页我们用 next 数组加速了匹配，但细想一步：失配时我们只知道「前面有多长的前后缀相等」，却完全没看失配的那个字符长什么样——它可能白跳一步。
导航只算路长却不看前方是否封路，对应 next 不看失配字符
缺陷实例图解
顺着箭头看一次失配后的跳转流程：绿色判断点是关键——跳转目标若与失配字符相同，这次比较注定失败。
以卵击石：无谓的比较
前一页看到：aba cab 失配后跳到下一个 a，还是撞上同一个 c。这不是运气差——跳过去的新字符，很可能和原来失配的那个字符一模一样，白比一次。
换一个人还是接不住同一个球，就该直接换到接得住的人
前车之覆：失败从何而来
逐帧回放一次失配，看清比较浪费在哪一帧。
后车之鉴：构造nextval
沿 next 递推链逐层回溯，把字符相同的跳转修正为 nextval。
nextval的代码实现
在求出 next 的同一循环里多比一个字符，直接得到 nextval。
高亮处是 nextval 与 next 的唯一区别：求完 j 后再比一次 T[i] 与 T[j]，不等照抄 next，相等则直接继承 nextval[j]，把必然失败的对齐跳过。
可视对比：next vs nextval
两套跳转表长得很像，边界一变结果就不同。逐条对照、数清比较次数，才能真正分清谁在何时占优。
- 跳转值仅由模式串自身前缀推出
- 失配后可能重复比较相同字符
- 构造简单，坏情形多一轮无谓比较
- 在 next 基础上追加字符相等的判断
- 失配后直接跳过必然失败的比较
- 构造多一步判断，坏情形省去冗余比较
自测：算一个nextval
模式串 "aaab" 的 next 数组为 [-1,0,1,2]，它的 nextval 数组是？
课后思考
先合上页面自己想，再看参考答案——答案只是思考路径，不是终点。
参考答案试着画出两者的 next/nextval 数组，逐位对比失配时的跳转目标。重复字符越多，next 盲区越大，nextval 省掉的回跳也越多。
参考答案从跳转逻辑看：nextval 只是提前排除了注定失败的比较，跳转步数本身不变。想清楚这一点，就知道答案和边界在哪里。
参考答案想想 Sunday、Boyer-Moore、AC 自动机等：本质都是用预处理的表记录失败后该从哪继续。找一个你能说清映射关系的场景即可。