String Matching: Berechnung des längsten Präfix-Suffix-Arrays im Kmp-Algorithmus

Question

KMP algorithm for string matching. Im Anschluss an den code ich online zur Berechnung des längsten Präfix-Suffix-Array gefunden:
Defination:

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

Code:

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++; 
     } 
     } 
    } 
} 

Kann ich len = len-1 statt len = lps[len-1]?
weil len immer die Präfixlänge wie aus [0 .. someIndex] zählt. Warum dann lps für die Zuweisung hier? Im Anschluss an die Fälle sind, für die ich die feinen getestet arbeiten (erste Zeile ist das Muster und die nachfolgenden zwei Linien sind das Ergebnis für Original und modifizierte Zuordnung zu 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 

-Code hier mit beiden Varianten geschrieben: http://ideone.com/qiSrUo

Answer 1

einen Fall verfolgt, für die es nicht funktioniert:

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 

Der Grund dafür ist:

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]) 

Also bis i = 3 hatten wir AB (0-1) als das Präfix, das mit Suffix AB (2-3) zusammenpasste, aber jetzt bei i = 4 gibt es eine Nichtübereinstimmung, so dass wir nicht sehen können Erweitern Sie das ursprüngliche Präfix (0-1), so dass die zu überprüfende Position das Präfix vor "AB" ist, was durch lps [len-1] < -1 erfolgt, da das Array von 0 beginnt und dies nicht unbedingt ist len-1, da wir möglicherweise noch einen Schritt zurückgehen müssen, um das neue längste Präfix-Suffix zu erhalten.

Answer 2

Hier ist die beste Erklärung, die ich je gesehen habe. Beispiel darin wird Ihre Frage klar beantworten.

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

Answer 3

Hier ist meine KMP-Code: -

#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; 
} 

Zeit Complexcity ist O (N)