4.2.2.1 next数组的手算方法
原书定位
印刷页P114起,对应PDF第126页。下文为目视整理的知识提要;完整内容见原书对照。
本书常用模式位置从 1 开始、next[1]=0 的约定; 时:
即考察失配字符之前的子串,求最长相等真前后缀长度后加 1。abcac 的 next 为 0,1,1,1,2。0 表示模式首字符也不匹配,随后主串前进一步,从模式首位重新开始。
有的题采用 0 起算、首值 -1 的版本;整体平移下标后值也要相应变化。next 是下次比较位置,PM 是前后缀长度,两者含义不同。

模式串abcac的next数组,原书P115。
对应练习
关联知识
原书对照
展开原书对照截图

