字符串匹配：使用kmp算法計算最長的前綴後綴數組

Question

KMP algorithm for string matching。 以下是我在網上找到了計算的最長前綴後綴數組code：
認定中：

lps[i] = the longest proper prefix of pat[0..i] 
       which is also a suffix of pat[0..i]. 

代碼：

void computeLPSArray(char *pat, int M, int *lps) 
{ 
    int len = 0; // length of the previous longest prefix suffix 
    int i; 

    lps[0] = 0; // lps[0] is always 0 
    i = 1; 

    // the loop calculates lps[i] for i = 1 to M-1 
    while(i < M) 
    { 
     if(pat[i] == pat[len]) 
     { 
     len++; 
     lps[i] = len; 
     i++; 
     } 
     else // (pat[i] != pat[len]) 
     { 
     if(len != 0) 
     { 
      // This is tricky. Consider the example AAACAAAA and i = 7. 
      len = lps[len-1]; //***************** 

      // Also, note that we do not increment i here 
     } 
     else // if (len == 0) 
     { 
      lps[i] = 0; 
      i++; 
     } 
     } 
    } 
} 

我可以用len = len-1代替len = lps[len-1]？
因爲len始終像從[0 .. someIndex]那樣計算前綴長度。那麼爲什麼要在這裏使用lps進行分配？以下是我測試了其正常工作的情況下（第一行是圖案和隨後的兩行是原始和改進分配的結果len）：

a a a b a b c 
0 1 2 0 1 0 0 
0 1 2 0 1 0 0 

a b c b a b c 
0 0 0 0 1 2 3 
0 0 0 0 1 2 3 

a a b c b a b 
0 1 0 0 0 1 0 
0 1 0 0 0 1 0 

代碼在這裏有兩個變化寫着：http://ideone.com/qiSrUo

Answer 1

以下爲它不工作的情況下：

i  0 1 2 3 4 5 
p  A B A B B A 
c1 0 0 1 2 0 1 
c2 0 0 1 2 2 3 

其原因是：

At i=4, len=2 
p[i]='B' and p[len]='A' //Mismatch! 
lps string upto i=3: AB(0-1 prefix), (2-3 suffix) 
------------------------------- 
i=4 
Next charecter: B 
len=2 // longest prefix suffix length 
Charecter looking for : A (=p[len]) 

因此，直到i = 3，我們將AB（0-1）作爲與後綴AB（2-3）相匹配的前綴，但是現在在i = 4處存在不匹配，因此我們看到我們不能使用擴展了原始前綴（0-1），因此要檢查的位置是在數組從0開始時在由「lps [len-1] < -1」完成的「AB」之前找到的前綴，並且這不一定len-1，因爲我們可能需要退一步，以獲得新的最長前綴後綴。

Answer 2

下面是我見過的最好的解釋。其中的例子將清楚地回答你的問題。

Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)

Answer 3

這是我的KMP代碼： -

#include <bits/stdc++.h> 
using namespace std; 


int main(void){ 
    int t; 
    scanf("%d",&t); 
    while(t--){ 
     string s; 
     cin>>s; 
     int n = s.length(); 
     int arr[n]; 
     arr[0] = 0; 
     int len = 0; 
     for(int i = 1;i<n;){ 
      if(s[len]==s[i]){ 
       len++; 
       arr[i++] = len; 
      } 
      else{ 
       if(len!=0){ 
        len = arr[len-1]; 
       } 
       else{ 
        arr[i] = 0; 
        i++; 
       } 
      } 
     } 
     cout<<arr[n-1]<<endl; 
    } 


    return 0; 
} 

時間Complexcity是O（N）