4.2.2.3 KMP算法的实现

教材导航 · 第4章

原书定位

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

下面沿用字符下标从 1 开始的教材约定,next 已预处理:

int i = 1, j = 1;
while (i <= n && j <= m) {
    if (j == 0 || S[i] == P[j]) { ++i; ++j; }
    else j = next[j];
}
return j > m ? i - m : 0;

构造 next 时用相同的前缀回退思想;主串匹配时只在相等或模式退至哨兵位置时推进 i。统计字符比较次数时不要把 j==0 的哨兵处理算成实际字符比较。

对应练习

4.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P116,PDF第128页

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