1. 引言

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

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

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

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