KMP算法應(yīng)該是每一本《數(shù)據(jù)結(jié)構(gòu)》書都會講的，算是知名度最高的算法之一了，但很可惜，很多人壓根就沒看懂過~~~
之后也在很多地方也都經(jīng)常看到講解KMP算法的文章，這兩天花了點時間總結(jié)一下，有點小體會，我希望可以通過我自己的語言來把這個算法的一些細(xì)節(jié)梳理清楚，給大家發(fā)表這篇文章
什么是KMP算法
KMP是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的。其中第一位就是《計算機(jī)程序設(shè)計藝術(shù)》的作者??！
KMP算法要解決的問題就是在字符串（也叫主串）中的模式（pattern）定位問題。說簡單點就是我們平時常說的關(guān)鍵字搜索。模式串就是關(guān)鍵字（接下來稱它為P），如果它在一個主串（接下來稱為T）中出現(xiàn)，就返回它的具體位置，否則返回-1（常用手段）。
首先，對于這個問題有一個很單純的想法：從左到右一個個匹配，如果這個過程中有某個字符不匹配，就跳回去，將模式串向右移動一位。這有什么難的？
我們可以這樣初始化：
之后我們只需要比較i指針指向的字符和j指針指向的字符是否一致。如果一致就都向后移動，如果不一致，如下圖：
A和E不相等，那就把i指針移回第1位（假設(shè)下標(biāo)從0開始），j移動到模式串的第0位，然后又重新開始這個步驟：
基于這個想法我們可以得到以下的程序：
/** * 暴力破解法 *@paramts 主串 *@paramps 模式串 *@return如果找到，返回在主串中第一個字符出現(xiàn)的下標(biāo)，否則為-1 */intbf(char* t,inttlengthchar* p,intplength){inti =0;// 主串的位置intj =0;// 模式串的位置while(i < tlength && j < plength) {if(t[i] == p[j]) {// 當(dāng)兩個字符相同，就比較下一個i++; j++; }else{ i = i - j +1;// 一旦不匹配，i后退j =0;// j歸0} }if(j == plength) {returni - j; }else{return-1; }}
上面的程序是沒有問題的，但不夠好！
（借用數(shù)字老師的一句話：我不能說你錯，只能說你不對~~~）
如果是人為來尋找的話，肯定不會再把i移動回第1位，因為主串匹配失敗的位置前面除了第一個A之外再也沒有A了，我們?yōu)槭裁茨苤乐鞔懊嬷挥幸粋€A？因為我們已經(jīng)知道前面三個字符都是匹配的?。ㄟ@很重要）。移動過去肯定也是不匹配的！有一個想法，i可以不動，我們只需要移動j即可，如下圖：
上面的這種情況還是比較理想的情況，我們最多也就多比較了再次。但假如是在主串“SSSSSSSSSSSSSA”中查找“SSSSB”，比較到最后一個才知道不匹配，然后i回溯，這個的效率是顯然是最低的。
大牛們是無法忍受“暴力破解”這種低效的手段的，于是他們?nèi)齻€研究出了KMP算法。其思想就如同我們上邊所看到的一樣：“利用已經(jīng)部分匹配這個有效信息，保持i指針不回溯，通過修改j指針，讓模式串盡量地移動到有效的位置。”
所以，整個KMP的重點就在于當(dāng)某一個字符與主串不匹配時，我們應(yīng)該知道j指針要移動到哪？
接下來我們自己來發(fā)現(xiàn)j的移動規(guī)律：
如圖：C和D不匹配了，我們要把j移動到哪？顯然是第1位。為什么？因為前面有一個A相同?。?/p>
如下圖也是一樣的情況：
可以把j指針移動到第2位，因為前面有兩個字母是一樣的：
至此我們可以大概看出一點端倪，當(dāng)匹配失敗時，j要移動的下一個位置k。存在著這樣的性質(zhì)：最前面的k個字符和j之前的最后k個字符是一樣的。
如果用數(shù)學(xué)公式來表示是這樣的
P[0 ~ k-1] == P[j-k ~ j-1]
這個相當(dāng)重要，如果覺得不好記的話，可以通過下圖來理解：
弄明白了這個就應(yīng)該可能明白為什么可以直接將j移動到k位置了。
因為:
當(dāng)T[i] != P[j]時
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]
公式很無聊，能看明白就行了，不需要記住。
這一段只是為了證明我們?yōu)槭裁纯梢灾苯訉移動到k而無須再比較前面的k個字符。
好，接下來就是重點了，怎么求這個（這些）k呢？因為在P的每一個位置都可能發(fā)生不匹配，也就是說我們要計算每一個位置j對應(yīng)的k，所以用一個數(shù)組next來保存，next[j] = k，表示當(dāng)T[i] != P[j]時，j指針的下一個位置。
很多教材或博文在這個地方都是講得比較含糊或是根本就一筆帶過，甚至就是貼一段代碼上來，為什么是這樣求？怎么可以這樣求？根本就沒有說清楚。而這里恰恰是整個算法最關(guān)鍵的地方。
int* getNext(char *p,intlength) {int*next= (int*)malloc(sizeof(int)*length);next[0] =-1;intj =0;intk =-1;while(j
這個版本的求next數(shù)組的算法應(yīng)該是流傳最廣泛的，代碼是很簡潔?？墒钦娴暮茏屓嗣坏筋^腦，它這樣計算的依據(jù)到底是什么？
好，先把這個放一邊，我們自己來推導(dǎo)思路，現(xiàn)在要始終記住一點，next[j]的值（也就是k）表示，當(dāng)P[j] != T[i]時，j指針的下一步移動位置。
先來看第一個：當(dāng)j為0時，如果這時候不匹配，怎么辦？
像上圖這種情況，j已經(jīng)在最左邊了，不可能再移動了，這時候要應(yīng)該是i指針后移。所以在代碼中才會有next[0] = -1;這個初始化。
如果是當(dāng)j為1的時候呢？
顯然，j指針一定是后移到0位置的。因為它前面也就只有這一個位置了~~~
下面這個是最重要的，請看如下圖：
請仔細(xì)對比這兩個圖。
我們發(fā)現(xiàn)一個規(guī)律：
當(dāng)P[k] == P[j]時，
有next[j+1] == next[j] + 1
其實這個是可以證明的：
因為在P[j]之前已經(jīng)有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
這時候現(xiàn)有P[k] == P[j]，我們是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1。
這里的公式不是很好懂，還是看圖會容易理解些。
那如果P[k] != P[j]呢？比如下圖所示：
像這種情況，如果你從代碼上看應(yīng)該是這一句：k = next[k];為什么是這樣子？你看下面應(yīng)該就明白了。
現(xiàn)在你應(yīng)該知道為什么要k = next[k]了吧！像上邊的例子，我們已經(jīng)不可能找到[ A，B，A，B ]這個最長的后綴串了，但我們還是可能找到[ A，B ]、[ B ]這樣的前綴串的。所以這個過程像不像在定位[ A，B，A，C ]這個串，當(dāng)C和主串不一樣了（也就是k位置不一樣了），那當(dāng)然是把指針移動到next[k]啦。
有了next數(shù)組之后就一切好辦了，我們可以動手寫KMP算法了：
intKMP(char*t,inttLength,char*p,intpLength+) {inti =0;// 主串的位置intj =0;// 模式串的位置int*next= getNext(ps);while(i < tLength && j < pLength) {if(j == -1|| t[i] == p[j]) {// 當(dāng)j為-1時，要移動的是i，當(dāng)然j也要歸0i++; j++; }else{// i不需要回溯了// i = i - j + 1;j =next[j];// j回到指定位置} }if(j == pLength) {returni - j; }else{return-1; }}
和暴力破解相比，就改動了4個地方。其中最主要的一點就是，i不需要回溯了。
最后，來看一下上邊的算法存在的缺陷。來看第一個例子：
顯然，當(dāng)我們上邊的算法得到的next數(shù)組應(yīng)該是[ -1，0，0，1 ]
所以下一步我們應(yīng)該是把j移動到第1個元素咯：
不難發(fā)現(xiàn)，這一步是完全沒有意義的。因為后面的B已經(jīng)不匹配了，那前面的B也一定是不匹配的，同樣的情況其實還發(fā)生在第2個元素A上。
顯然，發(fā)生問題的原因在于P[j] == P[next[j]]。
所以我們也只需要添加一個判斷條件即可：
int* getNext(char *p,intlength) {int*next= (int*)malloc(sizoef(int) *length);next[0] =-1;intj =0;intk =-1;while(j
好了，至此。KMP算法也結(jié)束了。
很奇怪，好像不是很難的東西怎么就把大家困住這么久呢？
仔細(xì)想想還是因為學(xué)習(xí)太浮躁了，很多東西總是草草應(yīng)付，很多細(xì)節(jié)都沒弄清楚，就以為自己懂了。結(jié)果就只能是似懂非懂的。要學(xué)東西真的需要靜下心來。
