4.2.3 KMP算法的进一步优化
原书定位
印刷页P117起,对应PDF第129页。下文为目视整理的知识提要;完整内容见原书对照。
若失配后即将比较的模式字符仍等于刚才失配的模式字符,该次比较必然再次失败,可继续跳转。1 起算版本:
首项置 0,并注意哨兵不作为真实字符访问。aaab 的 next=0,1,2,3,nextval=0,0,0,3。优化减少无效比较,渐近复杂度仍为 。

图4.5 nextval跳过重复比较,原书P117。
对应练习
关联知识
- 4.2 串的模式匹配
- 4.2.1 简单的模式匹配算法
- 4.2.2 串的模式匹配算法——KMP算法
- 4.2.2.1 next数组的手算方法
- 4.2.2.2 next数组的推导公式
- 4.2.2.3 KMP算法的实现
原书对照
展开原书对照截图

