4.2.1 简单的模式匹配算法
原书定位
印刷页P111起,对应PDF第123页。下文为目视整理的知识提要;完整内容见原书对照。
设主串长 、模式长 ,从每个可能起点逐字符比较;失配后主串改到本趟起点的下一位,模式回到首位。按教材 1 起算的指针写法,失配时 i=i-j+2; j=1;。
最坏比较次数为 ,常简记 ;额外空间 。重复前缀多时会反复比较,正是 KMP 的改进对象。

图4.2 简单模式匹配逐趟过程,原书P112。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P111起,对应PDF第123页。下文为目视整理的知识提要;完整内容见原书对照。
设主串长 、模式长 ,从每个可能起点逐字符比较;失配后主串改到本趟起点的下一位,模式回到首位。按教材 1 起算的指针写法,失配时 i=i-j+2; j=1;。
最坏比较次数为 ,常简记 ;额外空间 。重复前缀多时会反复比较,正是 KMP 的改进对象。

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

