4.2.3 KMP算法的进一步优化

教材导航 · 第4章

原书定位

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

若失配后即将比较的模式字符仍等于刚才失配的模式字符,该次比较必然再次失败,可继续跳转。1 起算版本:

nextval[j]={next[j],P[j]≠P[next[j]]nextval[next[j]],P[j]=P[next[j]]nextval[j]=\begin{cases}next[j],&P[j]\ne P[next[j]]\\nextval[next[j]],&P[j]=P[next[j]]\end{cases}

首项置 0,并注意哨兵不作为真实字符访问。aaab 的 next=0,1,2,3,nextval=0,0,0,3。优化减少无效比较,渐近复杂度仍为 O(n+m)O(n+m)。

图4.5 nextval跳过重复比较

图4.5 nextval跳过重复比较,原书P117。

对应练习

4.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P117,PDF第129页

原书对照,原书P118,PDF第130页