4.2.1 简单的模式匹配算法

教材导航 · 第4章

原书定位

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

设主串长 nn、模式长 mm,从每个可能起点逐字符比较;失配后主串改到本趟起点的下一位,模式回到首位。按教材 1 起算的指针写法,失配时 i=i-j+2; j=1;。

最坏比较次数为 O((n−m+1)m)O((n-m+1)m),常简记 O(nm)O(nm);额外空间 O(1)O(1)。重复前缀多时会反复比较,正是 KMP 的改进对象。

图4.2 简单模式匹配逐趟过程

图4.2 简单模式匹配逐趟过程,原书P112。

对应练习

4.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P111,PDF第123页

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