4.3 归纳总结与思维拓展

教材导航 · 第4章

原书定位

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

KMP 复用模式串内部的前后缀关系,主串不回溯。复习时先理解“失配之前已匹配了多少”,再求 next 或 nextval,最后模拟每次真实字符比较。

若要统计全部匹配,包括重叠匹配,找到一次后不能跳过整个已匹配区间;应按完整模式的最长相等真前后缀继续匹配。实现时可用前缀函数保留当前已匹配长度,并在每次完整匹配后回退到可复用的最长前缀。

关联知识

原书对照

展开原书对照截图

原书对照,原书P123,PDF第135页