了解KMP

初時KMP算法

       KMP算法是一種改進的字元串比對算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發現，是以人們稱它為克努特——莫裡斯——普拉特操作（簡稱KMP算法）。KMP算法的關鍵是利用比對失敗後的資訊，盡量減少模式串與主串的比對次數以達到快速比對的目的。具體實作就是實作一個next()函數，函數本身包含了模式串的局部比對資訊。時間複雜度O(m+n)。

基礎前提

1.字首字尾最長公共元素長度

       最長字首：以第一個字元開始的子串（但是不包括最後一個字元）。

       最長字尾：從最後一個字元結束的子串（但是不包括第一個字元）。

       最長公共元素就是，字首與字尾完全比對時，包含的最多的字元數。

    舉例：字元串“ababc"，其各個子串的最長公共元素長度如下表所示：

字元串	a	b	a	b	c
最大字首字尾公共元素長度	1	2

     比如，對于字元串 "aba"來說，它有長度為1的相同字首字尾 “a"；而對于字元串 "abab"來說，它有長度為2的相同字首字尾 "ab"

2.next數組

        next數組考慮的是，除目前字元外的最長相同字首字尾，是以，可以看出其與最長公共元素長度存在關系。

        規則為：将“ababc"對應的最長公共元素長度表的數值，依次向右移動一位，然後賦初值為-1。得到下表：

字元串	a	b	a	b	c
最大字首字尾公共元素長度	1	2
next數組	-1	1	2

next數組作用

       KMP的next數組，相當于告訴我們，當模式串中的某個字元跟源文本串中的某個字元比對失敗時，模式串下一步應該跳到哪個位置。如模式串中在j處的字元跟文本串在i處的字元不比對，下一步就用，next[j]處的字元繼續跟文本串i處的字元比對（即j=next[j]，相當于模式串向右移動了j-next[j]位）。圖示分析如下：

如何求得next數組

       基于之前的了解，可知計算next數組最好的方法就是，采用遞推形式。

       規則如下：其中k和j都是模式串中的兩個下标值(k<j)，已知求得了next[j]=k，如何就next[j+1]？？？

         1.若p[k] == p[j]，則next[j+1] = next[j]+1 = k+1；

         2.若p[k] != p[j]，如果此時p[next[k]] == p[j]，則next[j+1] = next[k]+1；否則，繼續遞歸字首索引 k=next[k]，而後重複此過程。

       遞歸求next數組，代碼如下：

void GetNext(char []p, int []next){
    int pLen = p.length;
    next[0] = -1;
    int k = -1;
    int j = 0;
    while(j < pLen-1){
      //p[k]表示字首，p[j]表示字尾
      if(k==-1 || p[j]==p[k]){
         ++k;
         ++j;
         next[j] = k;
      }else{
         k = next[k];
      }
    }
}
           

KMP算法過程

       next數組是KMP的核心，上面已經得到了next數組。

       KMP的規則如下：目前源文本串S比對到i位置，模式串P比對到j位置

          1.如果j == -1，或者目前字元串比對成功(即S[i] == P[j])，則令i++,j++，繼續比對下一個字元；

          2.如果j != -1，且目前字元比對失敗(即S[i] != P[j])，則令i不變，j = next[j]。意味着失配時，模式串P相對于文本串S向右移動了 j-next[j]位（即：失配字元所在位置 - 失配字元對應的next值，且此值大于等于1）。【這裡是KMP算法的關鍵之處，以此避免了失配時，S中字元回溯産生的重複比對過程】。

       KMP代碼過程如下：

int Kmp(char []s, char[]p){
    int sLen = s.length;
    int pLen = p.length;
    int i = 0;
    int j = 0;
    while(i<sLen && j<pLen){
        if(j==-1 || s[i]==p[j]){//比對成功
           i++;
           j++;
        }else{//比對失敗
           j = next[j];
        }
    }
    if(j == pLen)
        return i-j;
    else
        return -1;
}