技術文章 » 字串匹配的KMP演算法和C語言程式碼，不需要思考就能理解＜/h1＞

字串匹配的KMP演算法和C語言程式碼，不需要思考就能理解＜/h1＞

2020-08-11 23:44:58

KMP演算法用於判斷一個字串是否包含另一個字串，如果包含就返回腳標。其實KMP演算法本身特別簡單，我看了幾篇本章都號稱簡單易懂，結果看得我雲裡霧裏，直到我看到了阮一峯:字串匹配的KMP演算法，才真正看懂。下文的第一部分基本上都是阮一峯文章的轉述，第二部分程式碼也是在網上其他地方找的。第三部分KMP演算法的理解，纔是筆者的東西，相信看了第三部分你會豁然開朗。

一、KMS演算法的處理過程

下面 下麪用 KMP演算法在字串"BBC ABCDAB ABCDABCDABDE"中尋找字串"ABCDABD"：

首先，字串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜尋詞"ABCDABD"的第一個字元，進行比較。因爲B與A不匹配，所以搜尋詞後移一位。

因爲B與A不匹配，搜尋詞再往後移。

就這樣，直到字串有一個字元，與搜尋詞的第一個字元相同爲止。

接着比較字串和搜尋詞的下一個字元，還是相同。

直到字串有一個字元，與搜尋詞對應的字元不相同爲止。

這時，最自然的反應是，將搜尋詞整個後移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因爲你要把"搜尋位置"移到已經比較過的位置，重比一遍。

一個基本事實是，當空格與D不匹配時，你其實知道前面六個字元是"ABCDAB"。KMP 演算法的想法是，設法利用這個已知資訊，不要把"搜尋位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。

怎麼做到這一點呢？可以針對搜尋詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產生的，後面再介紹，這裏只要會用就可以了。

    已知空格與D不匹配時，前面六個字元"ABCDAB"是匹配的。查表可知，最後一個匹配字元B對應的"部分匹配值"爲2，因此按照下面 下麪的公式算出向後移動的位數：

    移動位數 = 已匹配的字元數 - 對應的部分匹配值

    因爲 6 - 2 等於4，所以將搜尋詞向後移動 4 位。

移動完後，再比較，發現空格與Ｃ還是不匹配，於是搜尋詞還要繼續往後移。這時，已匹配的字元數爲2（"AB"），對應的"部分匹配值"爲0。所以，移動位數 = 2 - 0，結果爲 2，於是將搜尋詞向後移 2 位。

這時空格與A還是不匹配，繼續後移一位。（因爲搜尋詞已經移動到頭了，所以預設的移動距離爲1位）

這個時候發現能匹配了，於是又逐位比較，直到發現C與D不匹配。於是，移動位數 = 6 - 2，繼續將搜尋詞向後移動 4 位。

這下就完全匹配了。

下面 下麪介紹《部分匹配表》是如何產生的。

　　首先，要瞭解兩個概念："字首"和"後綴"。 "字首"指除了最後一個字元以外，一個字串的全部頭部組合；"後綴"指除了第一個字元以外，一個字串的全部尾部組合。

        比如「bread」這個字串的字首是除了最後一個字元「d」，還剩下"brea"，它的全部組合字串有："b"、"br"、"bre"、"brea"。

        「bread」這個字串的後綴是除了第一個字元「b」，還剩下"read"，它的全部組合字串有："r"、"re"、"rea"、"read"。

        "部分匹配值"就是"字首"和"後綴"的最長的共有元素的長度。以"ABCDABD"爲例，

－"A"的字首和後綴都爲空集，共有元素的長度爲0；

－"AB"的字首爲[A]，後綴爲[B]，共有元素的長度爲0；

－"ABC"的字首爲[A, AB]，後綴爲[BC, C]，共有元素的長度0；

－"ABCD"的字首爲[A, AB, ABC]，後綴爲[BCD, CD, D]，共有元素的長度爲0；

－"ABCDA"的字首爲[A, AB, ABC, ABCD]，後綴爲[BCDA, CDA, DA, A]，共有元素爲"A"，長度爲1；

－"ABCDAB"的字首爲[A, AB, ABC, ABCD, ABCDA]，後綴爲[BCDAB, CDAB, DAB, AB, B]，共有元素爲"AB"，長度爲2；

－"ABCDABD"的字首爲[A, AB, ABC, ABCD, ABCDA, ABCDAB]，後綴爲[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度爲0。

         "部分匹配值"其實還可以定義爲：把字串沿着中間的字元摺疊，字串首尾重疊的字元個數。

        比如「ABC」沿着字元「B」摺疊，首尾的「A」和「C」就不能重疊，所以"部分匹配值"爲0.

        "ABCDA"沿着字元「C」摺疊，首尾的「A」能重疊，所以"部分匹配值"爲1.

        "ABCDAB"沿着字元「C」和「D」的中間摺疊，首尾的「AB」能重疊，所以"部分匹配值"爲2.

二、C語言程式

        利用上面KMS的處理過程和部分匹配值的生成方法，就可以寫程式了：

  1. void cal_next(char *str, int *next, int len)
  2. {
  3.     next[0] = -1;//next[0]初始化爲-1，-1表示不存在相同的最大字首和最大後綴
  4.     int k = -1;//k初始化爲-1
  5.     for (int q = 1; q <= len-1; q++)
  6.     {
  7.         while (k > -1 && str[k + 1] != str[q])//如果下一個不同，那麼k就變成next[k]，注意next[k]是小於k的，無論k取任何值。
  8.         {
  9.             k = next[k];//往前回溯
  10.         }
  11.         if (str[k + 1] == str[q])//如果相同，k++
  12.         {
  13.             k = k + 1;
  14.         }
  15.         next[q] = k;//這個是把算的k的值（就是相同的最大字首和最大後綴長）賦給next[q]
  16.     }
  17. }
  18.  
  19. int KMP(char *str, int slen, char *ptr, int plen)
  20. {
  21.     int *next = new int[plen];
  22.     cal_next(ptr, next, plen);//計算next陣列
  23.     int k = -1;
  24.     for (int i = 0; i < slen; i++)
  25.     {
  26.         while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）
  27.             k = next[k];//往前回溯
  28.         if (ptr[k + 1] == str[i])
  29.             k = k + 1;
  30.         if (k == plen-1)//說明k移動到ptr的最末端
  31.         {
  32.             //cout << "在位置" << i-plen+1<< endl;
  33.             //k = -1;//重新初始化，尋找下一個
  34.             //i = i - plen + 1;//i定位到該位置，外層for回圈i++可以繼續找下一個（這裏預設存在兩個匹配字串可以部分重疊），感謝評論中同學指出錯誤。
  35.             return i-plen+1;//返回相應的位置
  36.         }
  37.     }
  38.     return -1;  
  39. }
  40.

測試程式：

  1.     char *str = "bacbababadababacambabacaddababacasdsd";
  2.     char *ptr = "ababaca";
  3.     int a = KMP(str, 36, ptr, 7);
  4.     return 0;

三、KMS的理解

當搜尋詞已經匹配了6個字元，最後一個字元不匹配時

傳統的做法是移動一位，然後重新比較

可是KMS卻是直接移動了6 - 2 =4位元：

這是爲什麼呢？

怎麼保證的移動1位、移動2位、移動3位時遇到的字串都不匹配，所以KMS能直接移動4位元，再去比較呢？

其實非常簡單，這就是字串沿中間摺疊後，首尾字元重疊個數（也就是部分匹配值）的作用所在。

下面 下麪我舉個例子就懂了：

比如要在字串「123456789」中找「4568」

當匹配到上圖的位置時，發現字元「7」和字元「8」不匹配，於是傳統的方法是向後移動一位：

而KMS的移動距離用公式計算爲：3-0=3位

KMS演算法把「4568」中已經匹配過的「456」，直接跳過去了。爲什麼這裏能直接把匹配過的字串「456「跳過去呢？

下面 下麪我們來討論，我們把已經匹配過的字元分5種情況：（以3個字元來舉例）

1）、已經匹配過的字串中，每個字元都不相同，如」456「

    如果是這種情況，毫無疑問是可以直接把已匹配的字元跳過去的。

2）、已經匹配過的字串中，每個字元都相同，如」444「

    這種情況，最多隻能移動1位，比如下面 下麪的例子：

3）、已經匹配過的字串中，首尾字元相同，如」454「

    這種情況，移動位數要大於1，小於等於2。比如：

移動一位後：

首字元會和中間的字元對齊，他們不相同。再移動一位，就可能完全匹配了，因此移動位數最多爲2。

4）、已經匹配過的字串中，首兩個字元相同，如」445「

移動一位：

最後兩個字元會和首兩個字元對齊，他們一定不相同。

移動兩位：

最後一個字元會和首字元對齊，他們一定不相同。因此移動位數最少爲3。

5）、已經匹配過的字串中，尾兩個字元相同，如」455「

同理，移動位數最少爲3。

        

        經過上面的例子分析，可以看出KMS演算法就是對已經匹配過的字串再次利用來提高效率的。

        KMS演算法可以一句話總結爲：已經匹配過的字串如果首尾有相同的字母，就要少移動相應的位數，否則，已經匹配了多少個字元，就可以移動多少位。