离线下载
PDF版 ePub版

v_JULY_v · 更新于 2018-11-28 11:00:43

1. 引言

本 KMP 原文最初写于 2 年多前的 2011 年 12 月,因当时初次接触 KMP,思路混乱导致写也写得混乱。所以一直想找机会重新写下 KMP,但苦于一直以来对 KMP 的理解始终不够,故才迟迟没有修改本文。

然近期因在北京开了个算法班,专门讲解数据结构、面试、算法,才再次仔细回顾了这个 KMP,在综合了一些网友的理解、以及跟我一起讲算法的两位讲师朋友曹博、邹博的理解之后,写了 9 张 PPT,发在微博上。随后,一不做二不休,索性将 PPT 上的内容整理到了本文之中(后来文章越写越完整,所含内容早已不再是九张 PPT 那样简单了)。

KMP 本身不复杂,但网上绝大部分的文章(包括本文的 2011 年版本)把它讲混乱了。下面,咱们从暴力匹配算法讲起,随后阐述 KMP 的流程 步骤、next 数组的简单求解 递推原理 代码求解,接着基于 next 数组匹配,谈到有限状态自动机,next 数组的优化,KMP 的时间复杂度分析,最后简要介绍两个 KMP 的扩展算法。

全文力图给你一个最为完整最为清晰的 KMP,希望更多的人不再被 KMP 折磨或纠缠,不再被一些混乱的文章所混乱,有何疑问,欢迎随时留言评论,thanks。

上一篇: 关于 下一篇: 暴力匹配算法