KMP算法完整教程
全稱:
Knuth_Morris_Pratt
Algorithm(KMP算法)
類型:
進階檢索算法
功能:
字元串比對查找
提出者:
D.E.Knuth(克努茲),J.H.Morris(莫瑞斯),V.R.Pratt(普萊特)
所屬領域:
資料結構學
應用場景:
統計軟體
時間複雜度:
O(m+n)
<b>一。原始比對字元串方法</b>
以前,我們要肉眼在一個長字元串中尋找一個關鍵字詞,比如在word文檔中找一個單詞,我們的世界觀決定的方法論就是窮舉法:挨個搜尋單詞的第一個字母,每找到一個就定位然後比對下一個字母,當比對錯誤時就會放棄之前的比對,沿着剛才的進度繼續搜尋首字母.
這種方法也叫作”暴力字元比對”,和早期計算機檢索算法共享着同樣的思想,其中被檢索的字元串資料庫叫做”主串”,檢索的字元串叫”模式串”.名字很怪異我也沒辦法.
于是依照這種算法我們可以編寫一個程式來實作它:
int Index(SString S,SString T,int
pos)
{
i=pos;j=1;
while(i<=S[0]&&j<=T[0])
{
if(S[i]==T[j]){++i;++j;}
else{i=i-j+2;j=1;}//主串指針回溯重新開始下一趟比對.
}
if(j>T[0])return i-T[0];
else return
0;
}
//傳回模式串T在主串S第pos之後部分中的位置，若不存在則函數值為0.
這裡要注意i和j的指針回溯問題，注意細節，具體如下圖：
然後問題就來了，這種算法在特定的情況下暴露出一些問題，在時間效率上不是很完美，因為它畢竟是一種窮舉法，也符合人們的第一感覺，但是并不是最優的解決方案。比如說當在模式串中比較到第5個字元時才發現不比對，那麼之前四個字元都完全比對，下一步就不需要再把模式串一位一位的向後移，而很可能直接把模式串向後移動四位就可以了，省去了三次比較，比如模式串是“aceddfaa”，主串是“acedabcd”的情況。
<b>二。初代KMP算法</b>
針對上面那個例子，我們可以展開思考，如果模式串比對到第j個字元不比對的話，接下來隻需要在主串中這個位置從模式串中第f（j）的字元開始比較就行了，而不需要從第一個開始。<b>而且f（j）隻與模式串中第j個字元以前的所有字元有關。</b>好了，這個f（j）我們用一個數組來存放，就是next【j】。求出next【j】就是KMP算法的核心。可以看出next【j】的值越小越好，優化的效率越高。
KMP的next數組求法是很不容易搞清楚的一部分，也是最重要的一部分。我這篇文章就以我自己的感悟來慢慢推導一下吧！保證你看完過後是知其然，也知其是以然。
如果你還不知道KMP是什麼，請先閱讀上面的連結，先搞懂KMP是要幹什麼。
下面我們就來說說KMP的next數組求法。
KMP的next數組簡單來說，假設有兩個字元串，一個是待比對的字元串strText,一個是要查找的關鍵字strKey。現在我們要在strText中去查找是否包含strKey，用i來表示strText周遊到了哪個字元，用j來表示strKey比對到了哪個字元。
如果是暴力的查找方法，當strText[i]和strKey[j]比對失敗的時候，i和j都要回退，然後從i-j的下一個字元開始重新比對。
而KMP就是保證i永遠不回退，隻回退j來使得比對效率有所提升。它用的方法就是利用strKey在失配的j為之前的成功比對的子串的特征來尋找j應該回退的位置。而這個子串的特征就是前字尾的相同程度。
是以next數組其實就是查找strKey中每一位前面的子串的前字尾有多少位比對，進而決定j失配時應該回退到哪個位置。
我知道上面那段廢話很難懂，下面我們看一個彩圖：
這個圖畫的就是strKey這個要查找的關鍵字字元串。假設我們有一個空的next數組，我們的工作就是要在這個next數組中填值。
下面我們用數學歸納法來解決這個填值的問題。
這裡我們借鑒數學歸納法的三個步驟（或者說是動态規劃？）：
1、初始狀态
2、假設第j位以及第j位之前的我們都填完了
3、推論第j+1位該怎麼填
初始狀态我們稍後再說，我們這裡直接假設第j位以及第j位之前的我們都填完了。也就是說，從上圖來看，我們有如下已知條件：
next[j] == k;
next[k] == 綠色色塊所在的索引;
next[綠色色塊所在的索引] ==
黃色色塊所在的索引;
這裡要做一個說明：圖上的色塊大小是一樣的（沒騙我？好吧，請忽略色塊大小，色塊隻是代表數組中的一位）。
我們來看下面一個圖，可以得到更多的資訊：
1.由"next[j] ==
k;"這個條件，我們可以得到A1子串
== A2子串（根據next數組的定義，前字尾那個）。
2.由"next[k] ==
綠色色塊所在的索引;"這個條件，我們可以得到B1子串
== B2子串。
3.由"next[綠色色塊所在的索引] ==
黃色色塊所在的索引;"這個條件，我們可以得到C1子串
== C2子串。
4.由1和2(A1 == A2，B1 ==
B2)可以得到B1
== B2 == B3。
5.由2和3(B1 == B2， C1 ==
C2)可以得到C1
== C2 == C3。
6.B2 == B3可以得到C3 == C4 ==
C1 == C2
上面這個就是很簡單的幾何數學，仔細看看都能看懂的。我這裡用相同顔色的線段表示完全相同的子數組，友善觀察。
接下來，我們開始用上面得到的條件來推導如果第j+1位失配時，我們應該填寫next[j+1]為多少？
next[j+1]即是找strKey從0到j這個子串的最大前字尾：
#：(#:在這裡是個标記，後面會用)我們已知A1 ==
A2，那麼A1和A2分别往後增加一個字元後是否還相等呢？我們得分情況讨論：
(1)如果str[k] ==
str[j]，很明顯，我們的next[j+1]就直接等于k+1。
用代碼來寫就是next[++j] =
++k;
(2)如果str[k] !=
str[j]，那麼我們隻能從已知的，除了A1，A2之外，最長的B1，B3這個前字尾來做文章了。
那麼B1和B3分别往後增加一個字元後是否還相等呢？
由于next[k] == 綠色色塊所在的索引，我們先讓k =
next[k]，把k挪到綠色色塊的位置，這樣我們就可以遞歸調用"#："标記處的邏輯了。
由于j+1位之前的next數組我們都是假設已經求出來了的，是以，上面這個遞歸總會結束，進而得到next[j+1]的值。
我們唯一欠缺的就是初始條件了：
next[0] = -1, k
= -1, j = 0
另外有個特殊情況是k為-1時，不能繼續遞歸了，此時next[j+1]應該等于0，即把j回退到首位。
即 next[j+1] = 0; 也可以寫成next[++j] =
這裡我們用Java來描述：
public
static
int[] getNext(String
ps)
char[] strKey =
ps.toCharArray();
int[] next =
new
int[strKey.length];
// 初始條件
int j =
int k =
-1;
next[0]
= -1;
// 根據已知的前j位推測第j+1位
while (j < strKey.length - 1)
if (k ==
-1 || strKey[j] == strKey[k])
next[++j] = ++k;
else
k = next[k];
return next;
<b>三。KMP算法的優化和改進</b>
KMP算法是可以被進一步優化的。
但是，如果此時發現p(i) ==
（1）next[0]= -1
意義：任何串的第一個字元的模式值規定為-1。
（2）next[j]= -1
意義：模式串T中下标為j的字元，如果與首字元
相同，且j的前面的1—k個字元與開頭的1—k
個字元不等（或者相等但T[k]==T[j]）（1≤k
如：T=”abCabCad” 則
next[6]=-1，因T[3]=T[6]
（3）next[j]=k
意義：模式串T中下标為j的字元，如果j的前面k個
字元與開頭的k個字元相等，且T[j] != T[k]
（1≤k
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].（1≤k
(4) next[j]=0
意義：除（1）（2）（3）的其他情況。
于是乎我們修正的NEXT數組的求法如下：
// 如果str[j + 1] == str[k +
1]，回退後仍然失配，是以要繼續回退
if (str[j + 1] == str[k +
1])
{
next[++j] = next[++k];
}
else
next[++j] = ++k;
return next;
好了，以上就是KMP算法的所有内容，我們可以看出，KMP算法的關鍵就是：利用比對失敗後的資訊，利用遞歸的思想為每一個字元算出一個“特征值”。最後，KMP算法适合在字元種類很稀疏的情況下适用：僅當模式與主串之間存在許多“部分比對”的情況下才顯得比“暴力比對”快，但是如果模式串中有太多相同的字元，就會略微降低KMP的優化效果。KMP算法還有一個進步特點就是：訓示主串的指針不需要回溯，對主串僅需從頭至尾掃描一遍。
（如需轉載請标明出處）
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)