4.2.2.3 KMP算法的实现
原书定位
印刷页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 的哨兵处理算成实际字符比较。
对应练习
关联知识
原书对照
展开原书对照截图

