說明：

在網(wǎng)上查了各種資料，終于對KMP算法有了透徹的了解，都說KMP特簡單，我咋沒有察覺呢？難道是智商不在線？或許都是騙紙？

還是進(jìn)入正題吧，整理整理大佬的blog

KMP算法簡介：

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)就是實(shí)現(xiàn)一個(gè)next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息。時(shí)間復(fù)雜度O(m+n)。

我們首先用一個(gè)圖來描述kmp算法的思想。在字符串S中尋找F，當(dāng)匹配到位置i時(shí)兩個(gè)字符串不相等，這時(shí)我們需要將字符串T向前移動。常規(guī)方法是每次向前移動一位，但是它沒有考慮前i-1位已經(jīng)比較過這個(gè)事實(shí)，所以效率不高。事實(shí)上，如果我們提前計(jì)算某些信息，就有可能一次前移多位。假設(shè)我們根據(jù)已經(jīng)獲得的信息知道可以前移k位，我們分析移位前后的T有什么特點(diǎn)。我們可以得到如下的結(jié)論：

• • A段字符串是F的一個(gè)前綴。
  • B段字符串是F的一個(gè)后綴。
  • A段字符串和B段字符串相等。

?所以前移k位之后，可以繼續(xù)比較位置i的前提是f的前i-1個(gè)位置滿足：長度為i-k-1的前綴A和后綴B相同。只有這樣，我們才可以前移k位后從新的位置繼續(xù)比較。

所以kmp算法的核心即是計(jì)算字符串F每一個(gè)位置之前的字符串的前綴和后綴公共部分的最大長度（不包括字符串本身，否則最大長度始終是字符串本身）。

獲得F每一個(gè)位置的最大公共長度之后，就可以利用該最大公共長度快速和字符串S比較。當(dāng)每次比較到兩個(gè)字符串的字符不同時(shí)，我們就可以根據(jù)最大公共長度將字符串F向前移動(已匹配長度-最大公共長度)位，接著繼續(xù)比較下一個(gè)位置。事實(shí)上，字符串F的前移只是概念上的前移，只要我們在比較的時(shí)候從最大公共長度之后比較F和S即可達(dá)到字符串f前移的目的。

三：next數(shù)組計(jì)算：

　　理解了kmp算法的基本原理，下一步就是要獲得字符串f每一個(gè)位置的最大公共長度。這個(gè)最大公共長度在算法導(dǎo)論里面被記為next數(shù)組。在這里要注意一點(diǎn)，next數(shù)組表示的是長度，下標(biāo)從1開始；但是在遍歷原字符串時(shí)，下標(biāo)還是從0開始。假設(shè)我們現(xiàn)在已經(jīng)求得next[1]、next[2]、……next[i]，分別表示長度為1到i的字符串的前綴和后綴最大公共長度，現(xiàn)在要求next[i+1]。由上圖我們可以看到，如果位置i和位置next[i]處的兩個(gè)字符相同（下標(biāo)從零開始），則next[i+1]等于next[i]加1。如果兩個(gè)位置的字符不相同，我們可以將長度為next[i]的字符串繼續(xù)分割，獲得其最大公共長度next[next[i]]，然后再和位置i的字符比較。這是因?yàn)殚L度為next[i]前綴和后綴都可以分割成上部的構(gòu)造，如果位置next[next[i]]和位置i的字符相同，則next[i+1]就等于next[next[i]]加1。如果不相等，就可以繼續(xù)分割長度為next[next[i]]的字符串，直到字符串長度為0為止。由此我們可以寫出求next數(shù)組的代碼：

void cal_next(char *str, int *next, int len) {next[0] = -1;//next[0]初始化為-1，-1表示不存在相同的最大前綴和最大后綴int k = -1;//k初始化為-1for (int q = 1; q <= len-1; q++){while (k > -1 && str[k + 1] != str[q])//如果下一個(gè)不同，那么k就變成next[k]，注意next[k]是小于k的，無論k取任何值。 {k = next[k];//往前回溯 }if (str[k + 1] == str[q])//如果相同，k++ {k = k + 1;}next[q] = k;//這個(gè)是把算的k的值（就是相同的最大前綴和最大后綴長）賦給next[q] } }

?

?

?

四：字符串匹配

　　計(jì)算完成next數(shù)組之后，我們就可以利用next數(shù)組在字符串S中尋找字符串F的出現(xiàn)位置。匹配的代碼和求next數(shù)組的代碼非常相似，因?yàn)槠ヅ涞倪^程和求next數(shù)組的過程其實(shí)是一樣的。假設(shè)現(xiàn)在字符串F的前i個(gè)位置都和從某個(gè)位置開始的字符串S匹配，現(xiàn)在比較第i+1個(gè)位置。如果第i+1個(gè)位置相同，接著比較第i+2個(gè)位置；如果第i+1個(gè)位置不同，則出現(xiàn)不匹配，我們依舊要將長度為i的字符串分割，獲得其最大公共長度next[i]，然后從next[i]繼續(xù)比較兩個(gè)字符串。這個(gè)過程和求next數(shù)組一致，所以可以匹配代碼如下：

int KMP(char *str, int slen, char *ptr, int plen) {int *next = new int[plen];cal_next(ptr, next, plen);//計(jì)算next數(shù)組int k = -1;for (int i = 0; i < slen; i++){while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）k = next[k];//往前回溯if (ptr[k + 1] == str[i])k = k + 1;if (k == plen-1)//說明k移動到ptr的最末端 {//cout << "在位置" << i-plen+1<< endl;//k = -1;//重新初始化，尋找下一個(gè)//i = i - plen + 1;//i定位到該位置，外層for循環(huán)i++可以繼續(xù)找下一個(gè)（這里默認(rèn)存在兩個(gè)匹配字符串可以部分重疊），感謝評論中同學(xué)指出錯(cuò)誤。return i-plen+1;//返回相應(yīng)的位置 }}return -1; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/GHzz/p/9147073.html

總結(jié)

以上是生活随笔為你收集整理的KMP算法--深入浅出的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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