4.2.2 串的模式匹配算法——KMP算法

教材导航 · 第4章

原书定位

印刷页P112起,对应PDF第124页。下文为目视整理的知识提要;完整内容见原书对照。

失配时主串指针不回退,模式指针按照预先计算的 next 跳转。关键在于已匹配部分的最长相等真前缀与真后缀:保留可继续利用的重合部分,跳过必然失败的起点。

模式串 abcac 的部分匹配值 PM 为 0,0,0,1,0。在第 jj 个字符失配,已匹配长度是 j−1j-1,右移量等于“已匹配长度减去其最长相等前后缀长度”。预处理与匹配合计 O(n+m)O(n+m),辅助数组 O(m)O(m)。

模式串abcac的部分匹配值表

模式串abcac的部分匹配值表,原书P113。

下级知识点

对应练习

4.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P112,PDF第124页

原书对照,原书P113,PDF第125页

原书对照,原书P114,PDF第126页