4.2.2.2 next数组的推导公式
原书定位
印刷页P115起,对应PDF第127页。下文为目视整理的知识提要;完整内容见原书对照。
设 next[j]=k。若 P[j]==P[k],可将已经相等的前后缀延长一位,故 next[j+1]=k+1;若不同,则尝试更短的相等前后缀,即反复令 k=next[k]。
最后找到可延长的前后缀,或退到哨兵位置。取最长可用前后缀可以避免跳过潜在匹配;模式移动量为 。next 只由模式串决定,与主串无关。

图4.3 模式串右滑到合适位置,原书P115。

图4.4 求模式串的next值,原书P116。
对应练习
关联知识
原书对照
展开原书对照截图

