1. 引言

本 KMP 原文最初寫于 2 年多前的 2011 年 12 月，因當時初次接觸 KMP，思路混亂導(dǎo)致寫也寫得混亂。所以一直想找機會重新寫下 KMP，但苦于一直以來對 KMP 的理解始終不夠，故才遲遲沒有修改本文。

然近期因在北京開了個算法班，專門講解數(shù)據(jù)結(jié)構(gòu)、面試、算法，才再次仔細回顧了這個 KMP，在綜合了一些網(wǎng)友的理解、以及跟我一起講算法的兩位講師朋友曹博、鄒博的理解之后，寫了 9 張 PPT，發(fā)在微博上。隨后，一不做二不休，索性將 PPT 上的內(nèi)容整理到了本文之中（后來文章越寫越完整，所含內(nèi)容早已不再是九張 PPT 那樣簡單了）。

KMP 本身不復(fù)雜，但網(wǎng)上絕大部分的文章（包括本文的 2011 年版本）把它講混亂了。下面，咱們從暴力匹配算法講起，隨后闡述 KMP 的流程 步驟、next 數(shù)組的簡單求解 遞推原理 代碼求解，接著基于 next 數(shù)組匹配，談到有限狀態(tài)自動機，next 數(shù)組的優(yōu)化，KMP 的時間復(fù)雜度分析，最后簡要介紹兩個 KMP 的擴展算法。

全文力圖給你一個最為完整最為清晰的 KMP，希望更多的人不再被 KMP 折磨或糾纏，不再被一些混亂的文章所混亂，有何疑問，歡迎隨時留言評論，thanks。