KMP算法怎么用

這篇文章主要介紹了KMP算法怎么用，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

說明

KMP算法看懂了覺得特別簡單，思路很簡單，看不懂之前，查各種資料，看的稀里糊涂，即使網(wǎng)上最簡單的解釋，依然看的稀里糊涂。
我花了半天時間，爭取用最短的篇幅大致搞明白這玩意到底是啥。
這里不扯概念，只講算法過程和代碼理解：

KMP算法求解什么類型問題

字符串匹配。給你兩個字符串，尋找其中一個字符串是否包含另一個字符串，如果包含，返回包含的起始位置。
如下面兩個字符串：

char *str = "bacbababadababacambabacaddababacasdsd";
char *ptr = "ababaca";

str有兩處包含ptr
分別在str的下標(biāo)10，26處包含ptr。

“bacbababadababacambabacaddababacasdsd”;\

問題類型很簡單，下面直接介紹算法

算法說明

一般匹配字符串時，我們從目標(biāo)字符串str（假設(shè)長度為n）的第一個下標(biāo)選取和ptr長度（長度為m）一樣的子字符串進行比較，如果一樣，就返回開始處的下標(biāo)值，不一樣，選取str下一個下標(biāo)，同樣選取長度為n的字符串進行比較，直到str的末尾（實際比較時，下標(biāo)移動到n-m）。這樣的時間復(fù)雜度是O(n*m)。

KMP算法：可以實現(xiàn)復(fù)雜度為O(m+n)

為何簡化了時間復(fù)雜度：
充分利用了目標(biāo)字符串ptr的性質(zhì)（比如里面部分字符串的重復(fù)性，即使不存在重復(fù)字段，在比較時，實現(xiàn)最大的移動量）。
上面理不理解無所謂，我說的其實也沒有深刻剖析里面的內(nèi)部原因。

考察目標(biāo)字符串ptr：
ababaca
這里我們要計算一個長度為m的轉(zhuǎn)移函數(shù)next。

next數(shù)組的含義就是一個固定字符串的最長前綴和最長后綴相同的長度。

比如：abcjkdabc，那么這個數(shù)組的最長前綴和最長后綴相同必然是abc。
cbcbc，最長前綴和最長后綴相同是cbc。
abcbc，最長前綴和最長后綴相同是不存在的。

**注意最長前綴：是說以第一個字符開始，但是不包含最后一個字符。
比如aaaa相同的最長前綴和最長后綴是aaa。**
對于目標(biāo)字符串ptr，ababaca，長度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分別計算的是
a，ab，aba，abab，ababa，ababac，ababaca的相同的最長前綴和最長后綴的長度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最長前綴和最長后綴是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next數(shù)組的值是[-1,-1,0,1,2,-1,0]，這里-1表示不存在，0表示存在長度為1，2表示存在長度為3。這是為了和代碼相對應(yīng)。

下圖中的1，2，3，4是一樣的。1-2之間的和3-4之間的也是一樣的，我們發(fā)現(xiàn)A和B不一樣；之前的算法是我把下面的字符串往前移動一個距離，重新從頭開始比較，那必然存在很多重復(fù)的比較?，F(xiàn)在的做法是，我把下面的字符串往前移動，使3和2對其，直接比較C和A是否一樣。

代碼解析

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

KMP

這個和next很像，具體就看代碼，其實上面已經(jīng)大概說完了整個匹配過程。

int KMP(char *str, int slen, char *ptr, int plen)
{
  int *next = new int[plen];
  cal_next(ptr, next, plen);//計算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;//重新初始化，尋找下一個
      //i = i - plen + 1;//i定位到該位置，外層for循環(huán)i++可以繼續(xù)找下一個（這里默認(rèn)存在兩個匹配字符串可以部分重疊），感謝評論中同學(xué)指出錯誤。
      return i-plen+1;//返回相應(yīng)的位置
    }
  }
  return -1; 
}

測試

  char *str = "bacbababadababacambabacaddababacasdsd";
  char *ptr = "ababaca";
  int a = KMP(str, 36, ptr, 7);
  return 0;

注意如果str里有多個匹配ptr的字符串，要想求出所有的滿足要求的下標(biāo)位置，在KMP算法需要稍微修改一下。見上面注釋掉的代碼。

復(fù)雜度分析

next函數(shù)計算復(fù)雜度是(m)，開始以為是O(m^2)，后來仔細(xì)想了想，cal__next里的while循環(huán)，以及外層for循環(huán)，利用均攤思想，其實是O(m)，這個以后想好了再寫上。

………………………………………..分割線……………………………………..
其實本文已經(jīng)結(jié)束，后面的只是針對評論里的疑問，我嘗試著進行解答的。

進一步說明（2018-3-14）

看了評論，大家對cal_next(..)函數(shù)和KMP()函數(shù)里的

while (k > -1 && str[k + 1] != str[q])
    {
      k = next[k];
    }

和

while (k >-1&& ptr[k + 1] != str[i])
      k = next[k];

這個while循環(huán)和k=next[k]很疑惑！
確實啊，我開始看這幾行代碼，相當(dāng)懵逼，這寫的啥啊，為啥這樣寫；后來上機跑了一下，慢慢了解到為何這樣寫了。這幾行代碼，可謂是對KMP算法本質(zhì)得了解非常清楚才能想到的。很牛逼！
直接看cal_next(..)函數(shù)：
首先我們看第一個while循環(huán)，它到底干了什么。

在此之前，我們先回到原程序。原程序里有一個大的for()循環(huán)，那這個for()循環(huán)是干嘛的？

這個for循環(huán)就是計算next[0]，next[1],…next[q]…的值。

里面最后一句next[q]=k就是說明每次循環(huán)結(jié)束，我們已經(jīng)計算了ptr的前(q+1)個字母組成的子串的“相同的最長前綴和最長后綴的長度”。（這句話前面已經(jīng)解釋了?。?這個“長度”就是k。

好，到此為止，假設(shè)循環(huán)進行到 第 q 次，即已經(jīng)計算了next[q]，我們是怎么計算next[q+1]呢？

比如我們已經(jīng)知道ababab，q=4時，next[4]=2（k=2，表示該字符串的前5個字母組成的子串ababa存在相同的最長前綴和最長后綴的長度是3，所以k=2,next[4]=2。這個結(jié)果可以理解成我們自己觀察算的，也可以理解成程序自己算的，這不是重點，重點是程序根據(jù)目前的結(jié)果怎么算next[5]的）.，那么對于字符串ababab，我們計算next[5]的時候，此時q=5, k=2（上一步循環(huán)結(jié)束后的結(jié)果）。那么我們需要比較的是str[k+1]和str[q]是否相等，其實就是str[1]和str[5]是否相等！，為啥從k+1比較呢，因為上一次循環(huán)中，我們已經(jīng)保證了str[k]和str[q]（注意這個q是上次循環(huán)的q）是相等的（這句話自己想想，很容易理解），所以到本次循環(huán)，我們直接比較str[k+1]和str[q]是否相等（這個q是本次循環(huán)的q）。
如果相等，那么跳出while()，進入if()，k=k+1，接著next[q]=k。即對于ababab，我們會得出next[5]=3。 這是程序自己算的，和我們觀察的是一樣的。
如果不等，我們可以用”ababac“描述這種情況。 不等，進入while()里面，進行k=next[k]，這句話是說，在str[k + 1] != str[q]的情況下，我們往前找一個k，使str[k + 1]==str[q]，是往前一個一個找呢，還是有更快的找法呢？ （一個一個找必然可以，即你把 k = next[k] 換成k- -也是完全能運行的（更正：這句話不對啊，把k=next[k]換成k–是不行的，評論25樓舉了個反例）。但是程序給出了一種更快的找法，那就是 k = next[k]。 程序的意思是說，一旦str[k + 1] != str[q]，即在后綴里面找不到時，我是可以直接跳過中間一段，跑到前綴里面找，next[k]就是相同的最長前綴和最長后綴的長度。所以，k=next[k]就變成，k=next[2]，即k=0。此時再比較str[0+1]和str[5]是否相等，不等，則k=next[0]=-1。跳出循環(huán)。
（這個解釋能懂不？）

以上就是這個cal_next()函數(shù)里的

while (k > -1 && str[k + 1] != str[q])
    {
      k = next[k];
    }

最難理解的地方的一個我的理解，有不對的歡迎指出。

復(fù)雜度分析：

分析KMP復(fù)雜度，那就直接看KMP函數(shù)。

int KMP(char *str, int slen, char *ptr, int plen)
{
  int *next = new int[plen];
  cal_next(ptr, next, plen);//計算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;//重新初始化，尋找下一個
      //i = i - plen + 1;//i定位到該位置，外層for循環(huán)i++可以繼續(xù)找下一個（這里默認(rèn)存在兩個匹配字符串可以部分重疊），感謝評論中同學(xué)指出錯誤。
      return i-plen+1;//返回相應(yīng)的位置
    }
  }
  return -1; 
}

這玩意真的不好解釋，簡單說一下：

從代碼解釋復(fù)雜度是一件比較難的事情，我們從

這個圖來解釋。

我們可以看到，匹配串每次往前移動，都是一大段一大段移動，假設(shè)匹配串里不存在重復(fù)的前綴和后綴，即next的值都是-1，那么每次移動其實就是一整個匹配串往前移動m個距離。然后重新一一比較，這樣就比較m次，概括為，移動m距離，比較m次，移到末尾，就是比較n次，O(n)復(fù)雜度。 假設(shè)匹配串里存在重復(fù)的前綴和后綴，我們移動的距離相對小了點，但是比較的次數(shù)也小了，整體代價也是O(n)。
所以復(fù)雜度是一個線性的復(fù)雜度。

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“KMP算法怎么用”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!