KMP 演算法

花了好幾個小時,總算對萬惡的(?)KMP演算法有點眉目,就讓在下來分享一下吧!
KMP演算法全名為Knuth-Morris-Pratt algorithm,其中knuth為鼎鼎大名的Donald Knuth !


KMP演算法主要分為兩部分,第一部份為對字串預處理,第二部分為實際比對,先來分享預處理的部分


預處理的原理如下,將所欲處理的字串,對其從頭開始的所有字串求出其最大前綴與後綴相等的長度(在此我稱呼他為字串函數),舉例來說,字串  AAABBA,其值會是012001,讀者可以自己試看看,然而這個演算法的精隨就在如何快速地做預處理,原理如下:利用邊界的概念,逐次推進,何謂邊界的概念呢,邊界即為目前處理到的前綴的最後一個位置,若邊界的下一個位置和後綴的下一個位置相等,則後綴下一個位置的字串函數的值即為後綴最後一位的字串函數值加一;若不相等呢?則利用目前以處理的字串,利用字串函數往前推進,因為所選取的前綴和後綴相同,差別只是在下一位的字符,所以只需要再做比對一個字符,直到出現邊界的下一個位置和前綴的下一個位置相等為止 =>這樣的複雜度和字串長度成正比

圖解:

字串可看成
SDS =>其中S代表相同字串,若皆不相同則為空字串,D表任意字串

每輪多比對新的字符
SDSN=>其中N為新字符,故我們須比較S+N是否會和S+D的第一個字符相同,若相同,則把前後綴都加一,若不同.由於S和S相同,故只需要對S取前後綴相同,在做同樣判定即可,以此類推



了解了預處理的概念後,實作KMP的方法有兩個版本
1.
我們可以先將所欲求的pattern(簡寫為P),和所與比對的字串(簡寫為T),將其相加,並在中間插入任意符號(不會出現在P和T中的符號),然後對新得到的字串做預處理,接著進行第二部分,實際比對,可發現若字串函數的值和pattern長度相等,則表示match,如此即所求
其複雜度為$O(P+T)$

2.
先對P做預處理,再把T和P做比對,其複雜度也為$O(P+T)$

c++ 程式碼如下

class Solution {
public:
    int index[100000];
    int pre[100000];
    int strStr(string haystack, string needle) {
          int target=haystack.size();
          int target1=needle.size();
          if(target1==0)
              return 0; 
          int q=-1;
          pre[0]=-1;
          for(int i=1;i<target1;i++)
          {
              while(needle[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(needle[i]==needle[q+1])
                  q++;
              pre[i]=q;
          }
          q=-1;
          for(int i=0;i<target;i++)
          {
              while(haystack[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(haystack[i]==needle[q+1])
              {
                  q++;
                  if(q==target1-1)
                      cout<<i-target1+1<<endl;
              }
          }
          return 0;  
    }
};

PS. 小魯的參考資料:
1. coursera
2. Introduction to algorithms