字元串匹配演算法—KMP

• 2019 年 10 月 7 日
• 筆記

在開始正文前先了解兩個概念

前綴：

　　除了字元串的最後一個字元外，一個字元串的全部頭部組合

後綴：

　　除了字元串的第一個字元外，一個字元串的全部尾部組合

例： 

　　abcd 的全部前綴為： a, ab, abc

　　abcd 的全部後綴為： d, cd, bcd

正文部分：

字元串匹配演算法的姊妹篇—BF演算法中講解了如何利用BF演算法暴力匹配。

但是在實際執行過程中這種演算法卻顯得很笨重，每一次遇到不匹配的字元時，txt與pattern都要同時回退。

第一次比較到pattern中的b與string中的c時，匹配失敗，i和j同時回退，但是很顯然，在pattern中並沒有字元c，因此我們只需要i移動到c的下一個字元a上，而讓j移動到pattern中第一個字元a再次進行匹配。

KMP演算法永不回退string的指針i（不重複掃描string），而是藉助next數組將pattern指針j移動到正確的位置。

如何找到正確的位置就比較重要，所以先來看個例子思考一下怎樣將指針j正確移動以避免重複匹配：

當匹配進行到上面這個狀態時，前面四個字元均以匹配，到第五個字元 c 與 a 不匹配，這裡我們將這種狀態稱為失配，將string[i]稱為失配字元。那麼 j 該如何移動才能保證匹配次數儘可能少呢？

經過觀察我們發現，pattern中有兩個子串很類似，分別是 aba 和 abc ，它們都有共同的前綴ab，唯一區別就是最後一個字元一個為a一個為c；

沒錯，KMP也發現了這個規律，於是KMP就開始偷懶啦：我現在這個位置若是將j回退到起始位置，有點虧，因為這裡有兩個前綴相同的子串 aba 和 abc，j當前處於失配字元c，如果我偷個懶只讓j回退到aba中最後一個a位置，萬一string中失配字元剛好是 a ，那我不就可以繼續匹配了。

 於是就產生了下面的移動， j 移動到 pattern[2]，i 依舊指向失配字元 a ， 哇，移動之後，太巧了吧，剛好匹配！KMP：還好沒有全部回退，我可真是個機靈鬼。

 OK，繼續幹活

 匹配成功！

在上面這個例子中當匹配到字元 c 時，發生了失配現象，這個時候 KMP 的做法並不是像BF那樣笨笨的將 j 全部回退 ，i + 1，然後重新從 i 開始一個個的與 j 匹配。而是 找到了aba 和 abc這兩個有公共前綴的子串，並讓 j 移動到了 aba中最後一個a 位置（與abc中c等價的位置），然後繼續將失配字元與 指針 j 字元進行匹配。

在上面這個過程中，pattern為 ababc，當 j 從 0 開始遍歷時，遍歷過的字元都會組成pattern的一個個子串。

例如：當 j = 0 時，當前子串為 a

　　   當 j = 1時，當前子串為 ab

          ….

          當 j = 4時，當前子串為 ababc

先列出 j 從 0 到 strlen(pattern)的所有經過的子串

 當 pattern[j] = ‘c’ 時，當前子串為 ababc，那麼就有兩種情況：字元’c’匹配成功 或 字元 ‘c’ 失配（事實上，當 j 遍歷 pattern中任意一個字元時，都會產生這兩種情況，失配或匹配）；匹配成功 i++, j++；這裡主要考慮失配後 j 的去向。

本例中，字元 ‘c’ 失配，j 由4變為了 2，如果將pattern中 j 遍歷到每一個字元失配後 j 的去向用一個數組存儲就產生了next。很顯然這裡，next[4] = 2，即失配後執行的操作為  j = next[j];（j = 4時，若pattern[j]失配則 j 移動到 2 繼續匹配）

假設我們已經求得了next數組，知道 j 每一步失配後應該去哪裡，那麼我們就產生了如下程式碼：

int KMP(char pattern[], char str[]) // pattern 為模式串  str為待搜索string串  {      int *next = next_arr(pattern);  // next_arr 為 獲取 next數組函數；int i = 0;      int j = 0; // 從第一個字元開始比較      while(str[i]){          if(j == -1 || str[i] == pattern[j]){ // 從頭重新匹配 或 匹配成功              ++i;++j;          }else{  // 失配              j = next[j];          }          if(j == strlen(pattern)){ // 判斷是否全部匹配正確              return i - j;  // 匹配正確返回 str 串中起始index          }      }      return -1; // 匹配失敗  }

還有一個問題是：next數組如何產生？

還記得在例子中我們提到的 有公共前綴 ab 的兩個子串 aba 和 abc 嗎？

當前 j = 4，形成子串為 ababc，字元’c’失配。我們說這裡發現了 “公共前綴”ab，那這個ab是怎麼得來的？在沒有任何知識儲備之前，我是拿眼睛看出來的。

在有了知識儲備之後，ab在abab（注意是abab而不是ababc）這個子串中被稱作前綴後綴公共元素，其長度被稱為前綴後綴公共元素的最大長度。什麼意思呢？

讓我們先列出abab的所有前綴和後綴。

 將前綴後綴一一對比，發現 ab 為前綴後綴公共元素，其長度為2，其餘一個元素的前後綴與三個元素的前後綴均不相等。

因此我們例子中瞎編的名詞 “公共前綴”ab 就是這麼得來的。

那得出這個 ab 有什麼用呢？而且這個 ab 是在子串 abab中得來的，和 已經遍歷到 字元 ‘c’的子串 ababc 又有什麼關係呢？

為了簡潔起見，我們將 abab 這個子串中前綴ab 簡稱 p-ab，後綴 ab 簡稱 s-ab。

無論 s-ab的下一個字元是什麼，只要失配則 j 需要回退，此時 j 僅僅只需要回退到 p-ab的下一個字元 a 即可，因為 p-ab 與 s-ab完全相同。

因此在 遍歷至子串 ababc 時， j 的回退位置(  next[j]  )實際是 它的前一個子串abab產生的前後綴公共元素最大長度的值。

故 想要知道當 j 遍歷到每一個pattern元素時失配後如何回退就必須得到 next 數組的值，因此就必須對 pattern 的每個子串求其前後綴公共元素最大長度，記為 MaxL; 

next 數組的值即是 MaxL 數組整體向右移動一位，最左邊next[0] 為 -1。

給出一張動態圖感受一下MaxL以及前後綴公共元素的求解過程。（每一行代表一個子串，最左邊一列為該行子串對應的前後綴公共元素最大長度，最終用黃色標註出的部分為前後綴公共元素）

  這樣我們就成功得出了next數組。其程式碼實現有兩種方式，一種是直接求取，一種是遞推求取。

1.直接求取

  偽碼描述

int *next_arr(char pattern[])  {      int len = strlen(pattern);      int *next = new int[len];      // next數組為 MaxL元素右移一位,next[0] = -1      // 因此next數組 next[i]的值為/***當前子串的前一個子串***/的前後綴公共元素最大長度      for(int j = 0; j < len; ++j){          // j 遍歷pattern，j處當前子串pattern[0...j]長度為 j+1          //                j處前一個子串pattern[0...j-1]長度為 j          //                j處前一個子串的最長前後綴長度為 j-1          // j == 0, next[j] = -1          // j == 1, 當前子串長度2,前一個子串長度1，無前後綴，next[j] = 0          // j > 1          　　int p; // p動態表示前後綴長度          　　// p由最大開始遞減（最短前後綴1 <= p <= 最長前後綴 j-1），          　　//      直到前後綴相等break跳出循環，所得長度即是pattern[0...j-1]的前後綴公共元素最大長度          　　for(p = j-1; p > 0; --p){            　　  // 前後綴相等break退出循環          　　}          　　// 若 p == 0，則沒有發現前後綴公共元素，next[j] = 0      }      return next;  }

程式碼實現

bool IsEqual(char*,int,int);  int *next_arr(char pattern[])  {      int len = strlen(pattern);      int *next = new int[len];      for(int j = 0; j < len; ++j){ // j標識當前子串，j值為前一個子串長度          if(j == 0){  // next[0] = -1              next[j] = -1;          }else if(j == 1){ // 一個元素的子串無前後綴              next[j] = 0;          }else{              int p;              for(p = j-1; p > 0; --p){ // p 標定所求子串前後綴長度，從最長j-1 開始遞減至 最短1                  if(IsEqual(pattern, p, j)){ // IsEqual判斷前綴pattern[0...p-1]後綴pattern[j-p,j-1]是否相等                      next[j] = p;                      break;                  }              }              if(p == 0){ // 當前子串沒有前後綴公共元素                  next[j] = 0;              }          }      }      return next;  }

bool IsEqual(char pattern[], int ps_len, int subPattern)  {      // ps_len為前後綴長度，subPattern為子串長度      // 判斷從 pattern[0...ps_len-1] 及 pattern[subPattern-ps_len...subPattern-1]的串是否相等      for(int i = 0; i < ps_len; ++i){          if(pattern[i] != pattern[subPattern - ps_len + i]){              return false;          }      }      return true;  }

直接求取模仿了依次從子串中求取前後綴公共元素的過程，時間複雜度較高

遞推求取則利用了一定的規律

2.遞推求取

先看一下為什麼可以採用遞推求取

 容易發現，在求取aba子串和abab子串的MaxL值時，abab這個子串就做的很不聰明，很明顯，abab這個子串比aba子串剛好多出一個 b，這就讓abab中恰好有一個p-ab和一個s-ab，MaxL值為2，如果不利用這個可能出現的巧合，那麼就只能將abab子串的所有前後綴列出一一比較求取，是不是很浪費時間。

 由於這是個遞推，程式碼行數很少光看程式碼不是很容易理解，所以我準備將整個過程過一遍方便理解：

先看一遍程式碼

int *next_arr(char pattern[])  {      int *next = new int[strlen(pattern)];      int i = 0;      int j = -1;      next[0] = -1;      while(i < strlen(pattern)-1){          if(j == -1 || pattern[i] == pattern[j]){              ++i;              ++j;              next[i] = j;          }else{              j = next[j];          }      }      return next;  }

動態圖演示

解釋：

　　next[0] = -1；

　　假設next[i] = j;  則  pattern[0…j-1] == pattern[i-j…i-1];

　　　　此時若 pattern[j] == pattern[i] ， 則 pattern[0…j] == pattern[i-j, i];  即 next[i+1] == j+1

　　　　若  pattern[j] != pattern[i] ，發生失配，此時只需要將 j 移動到正確的位置繼續判斷。即 j = next[j]; （這一部分思想與我們前面講過的在 string中 匹配 pattern串相似，str[i] != pattern[j]即失配， j = next[j] 繼續匹配）