??

?

KMP算法完整教程

?

?

全稱: ??????????????????????????????Knuth_Morris_Pratt Algorithm(KMP算法)

類型: ??????????????????????????????高級檢索算法

功能: ??????????????????????????????字符串匹配查找

提出者: ??????????????????????????D.E.Knuth(克努茲),J.H.Morris(莫瑞斯),V.R.Pratt(普萊特)

所屬領域:????????????????????????數據結構學

應用場景:????????????????????????統計軟件

時間復雜度:????????????????????O(m+n)

?

?

?

?

一。原始匹配字符串方法

?

????????以前,我們要肉眼在一個長字符串中尋找一個關鍵字詞,比如在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”的情況。

?

?

?

?

二。初代KMP算法

?

?

???????針對上面那個例子，我們可以展開思考，如果模式串匹配到第j個字符不匹配的話，接下來只需要在主串中這個位置從模式串中第f（j）的字符開始比較就行了，而不需要從第一個開始。而且f（j）只與模式串中第j個字符以前的所有字符有關。好了，這個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] = ++k;

?這里我們用Java來描述：

public?static?int[] getNext(String ps)

{

????char[] strKey = ps.toCharArray();

????int[] next =?new?int[strKey.length];

?

????// 初始條件

????int?j =?0;

????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;

}

?

?

?

三。KMP算法的優化和改進

?

KMP算法是可以被進一步優化的。

我們以一個例子來說明。譬如我們給的P字符串是“abcdaabcab”，經過KMP算法，應當得到“特征向量”如下表所示：

?

但是，如果此時發現p(i) == p(k），那么應當將相應的next[i]的值更改為next[k]的值。經過優化后可以得到下面的表格：

?

?

（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數組的求法如下：

public?static?int[] getNext(String ps)

{

????char[] strKey = ps.toCharArray();

????int[] next =?new?int[strKey.length];

?

????// 初始條件

????int?j =?0;

????int?k = -1;

????next[0] = -1;

?

????// 根據已知的前j位推測第j+1位

????while (j < strKey.length - 1)

????{

????????if (k == -1 || strKey[j] == strKey[k])

????????{

????????????// 如果str[j + 1] == str[k + 1]，回退后仍然失配，所以要繼續回退

????????????if (str[j + 1] == str[k + 1])

????????????{

????????????????next[++j] = next[++k];

????????????}

????????????else

????????????{

????????????????next[++j] = ++k;

????????????}

????????}

????????else

????????{

????????????k = next[k];

????????}

????}

?

?????return next;

}

?

???????好了，以上就是KMP算法的所有內容，我們可以看出，KMP算法的關鍵就是：利用匹配失敗后的信息，利用遞歸的思想為每一個字符算出一個“特征值”。最后，KMP算法適合在字符種類很稀疏的情況下適用：僅當模式與主串之間存在許多“部分匹配”的情況下才顯得比“暴力匹配”快，但是如果模式串中有太多相同的字符，就會略微降低KMP的優化效果。KMP算法還有一個進步特點就是：指示主串的指針不需要回溯，對主串僅需從頭至尾掃描一遍。

?

（如需轉載請標明出處）

?

??

轉載于:https://www.cnblogs.com/jinhengyu/p/10257842.html

總結

以上是生活随笔為你收集整理的!KMP算法完整教程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。