前言：

? 昨天看到《算法導論》里的第32章：字符串匹配，說到一個關于字符串匹配的很好的算法——KMP。關于KMP的內存含意以及KMP的來源，不是本文講述的范疇，請感興趣的讀者自行查閱相關資料。

? 本文主要是來說明KMP算法的思路和實現(xiàn)過程，以及它相比于樸素的字符串模式匹配存在的優(yōu)勢。

本文鏈接：http://blog.csdn.net/lemon_tree12138/article/details/48488813?--?編程小笙

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?--轉載請注明出處

樸素模式匹配算法：

1.思路分析

? 樸素的字符串模式匹配就是傳統(tǒng)的算法——逐個比較。因為使用了嵌套循環(huán)，所以效率比較低。

2.代碼實現(xiàn)

public class SimpleMatching {/*** 采用樸素的字符串匹配算法查找子字符串* * @param T* 主字符串* @param P* 匹配模式字符串* @return* 匹配成功的所有位置*/public List<Integer> getIndexOfPinT(String T, String P) {if (Tools.isEmptyString(T) || Tools.isEmptyString(P)) {return null;}List<Integer> indexs = new ArrayList<Integer>();char[] t = T.toCharArray();char[] p = P.toCharArray();for (int i = 0; i <= t.length - p.length; i++) {for (int j = 0; j < p.length; j++) {if (t[i + j] == p[j]) {if (j == p.length - 1) {indexs.add(i);}continue;}break;}}return indexs;} }

? 我們假定主字符串的長度為n，匹配模式字符串的長度為m。那么對于上面的算法，時間復雜度就是O(m*n)。對于一些需求不太嚴苛或是m,n比較小的情況下。這種算法還是可以接受的。但是如果不是上述情況，這樣的一個時間復雜度可能還是略顯尷尬。下面我就來介紹一下改進過后的KMP算法。

KMP模式匹配算法：

1.思路分析

? KMP算法的關鍵是為我們排除了一些重復匹配，使用主字符串的匹配位置“指針”不需要回溯。這里不妨列舉一個小例子。

? 主字符串T：fababadaaswababaca

? 匹配模式P：ababaca

? 假使此時我們正在匹配T的第7位(fababa[d]aaswababaca)和P的第6位(ababa[c]a)。而且匹配失敗了。針對樸素的匹配模式是T的“指針”回溯到(fa[b]abadaaswababaca)，P的“指針”回溯到([a]babaca)。這無疑是浪費了很多的時間。

? 我們重新檢查一下P(ababaca)，當我們開始匹配第6位的時候，之前的5位已經(jīng)匹配完成。而且，[aba]baca =?ab[aba]ca!那么針對于T而言，fab[aba]daaswababaca這三位是已經(jīng)匹配過了，我們在把與之前匹配相等的字符串移至此處時，是不是就說明，這幾個字符串是不需要再匹配了。

? 當我們知道了在匹配的過程中，有一些字符是不需要再匹配了的時候，接下來就是重頭戲了。如何讓這些已經(jīng)匹配過的字符串不再重復匹配？

? 通過上面的分析，其實已經(jīng)暗含了解決方案。就是我們要知道匹配模式中，每個最優(yōu)前綴(關于最優(yōu)前綴可以參考《算法導論》32章內容)S中，S的不為自身的最長的一個等于最優(yōu)后綴(關于最優(yōu)后綴可以參考《算法導論》32章內容)的最優(yōu)前綴SS。這句話可能聽起來有一些繞口，下面通過一個實例來說明：

??匹配模式P：ababaca

? 我們選取P的一個最優(yōu)前綴S = ababa,那么SS = aba.因為SS是S的最優(yōu)前綴，也是S的最優(yōu)后綴，而且是最長的。

? 上面就是關于KMP匹配模式的思路分析，如果你感覺這里有一些枯燥乏味或是閱讀困難(對此，我對我拙劣的文字描述表示一些歉意)。下面可以在代碼中尋找大家所契合的地方，因為邏輯是想通的嘛。

2.最優(yōu)前綴的形式：

Index 0123456 P ABABACA Next 0012301

3.代碼實現(xiàn)

(1)獲得字符串中的每個最優(yōu)前綴子字符串中的最長的最優(yōu)前綴等于最優(yōu)后綴的長度

/*** 獲得字符串中的每個最優(yōu)前綴子字符串中的* 最長的最優(yōu)前綴等于最優(yōu)后綴的長度* * @param text* 待計算的字符串* @return* 返回最長的最優(yōu)前綴等于最優(yōu)后綴的長度數(shù)組*/public int[] getNext(String text) {if (Tools.isEmptyString(text)) {return null;}int[] lengths = new int[text.length()];for (int i = 0; i < text.length(); i++) {String sub = text.substring(0, i + 1);int maxLen = 0;for (int j = 0; j < sub.length() - 1; j++) {String subChild = sub.substring(0, j + 1);if (sub.endsWith(subChild) && subChild.length() > maxLen) {maxLen = subChild.length();}}lengths[i] = maxLen;}return lengths;}

(2)獲得字符串P在字符串T中出現(xiàn)的所有位置

/*** 獲得字符串P在字符串T中出現(xiàn)的所有位置* * @param T* 主字符串* @param P* 匹配模式字符串* @return* 匹配成功的所有位置*/public List<Integer> getIndexOfPinT(String T, String P) {if (Tools.isEmptyString(T) || Tools.isEmptyString(P)) {return null;}List<Integer> indexs = new ArrayList<Integer>();char[] t = T.toCharArray();char[] p = P.toCharArray();int[] next = getNext(P);int indexT = 0;int indexP = 0;while (indexT < t.length) {if (t[indexT] == p[indexP]) {indexP++;indexT++;} else {if (indexP == 0) {indexT++;} else {indexP = next[indexP - 1];}}if (indexP == p.length) {indexs.add(indexT - indexP);indexP = 0;}}return indexs;}

參考說明：

1.《算法導論》

2.Knuth–Morris–Pratt algorithm

源碼下載：

對于上面的描述，如果你還沒有完全理解，可以在下面的鏈接中下載與本文相關的源碼進行參考學習.

http://download.csdn.net/detail/u013761665/9110859

總結

以上是生活随笔為你收集整理的算法：模式匹配之KMP算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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