4.2.2.1 next数组的手算方法

教材导航 · 第4章

原书定位

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

本书常用模式位置从 1 开始、next[1]=0 的约定;j≥2j\ge2 时:

next[j]=PM[j−1]+1next[j]=PM[j-1]+1

即考察失配字符之前的子串,求最长相等真前后缀长度后加 1。abcac 的 next 为 0,1,1,1,2。0 表示模式首字符也不匹配,随后主串前进一步,从模式首位重新开始。

有的题采用 0 起算、首值 -1 的版本;整体平移下标后值也要相应变化。next 是下次比较位置,PM 是前后缀长度,两者含义不同。

模式串abcac的next数组

模式串abcac的next数组,原书P115。

对应练习

4.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

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

原书对照,原书P115,PDF第127页