4.2.2 串的模式匹配算法——KMP算法
原书定位
印刷页P112起,对应PDF第124页。下文为目视整理的知识提要;完整内容见原书对照。
失配时主串指针不回退,模式指针按照预先计算的 next 跳转。关键在于已匹配部分的最长相等真前缀与真后缀:保留可继续利用的重合部分,跳过必然失败的起点。
模式串 abcac 的部分匹配值 PM 为 0,0,0,1,0。在第 个字符失配,已匹配长度是 ,右移量等于“已匹配长度减去其最长相等前后缀长度”。预处理与匹配合计 ,辅助数组 。

模式串abcac的部分匹配值表,原书P113。
下级知识点
对应练习
关联知识
- 1.2.2 算法效率的度量
- 4.2 串的模式匹配
- 4.2.1 简单的模式匹配算法
- 4.2.2.1 next数组的手算方法
- 4.2.2.2 next数组的推导公式
- 4.2.2.3 KMP算法的实现
- 4.2.3 KMP算法的进一步优化
原书对照
展开原书对照截图


