Ist diese Implementierung von KMP Pattern Matching-Algorithmus richtig?

Question

Ich lese über KMP von diesem Link: (http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/).

Ich habe die KMP anders als in der jeweiligen Link angegeben und es gibt die richtige Antwort auch, kann mir bitte jemand sagen, ob diese Umsetzung von KMP richtig oder falsch ist? Wenn dann falsch, dann erkläre freundlich für das gleiche.

Unten ist die Implementierung von mir:

package Algos.patternMatching; 

public class KMP { 

    public static void main(String[] args) { 
     KMPAlgo("ABABDABACDABABCABAB", "ABABCABAB"); 
    } 

    private static void KMPAlgo(String text, String pattern) {  //check whether right or wrong 
     int i = 0; 
     int j = 0; 

     int[] lps = LPS(pattern); 

     while (i < text.length() - pattern.length() + 1) { 

      while (j < pattern.length() && pattern.charAt(j) == text.charAt(i)) { 

       j++; 
       i++; 
      } 

      if (j == pattern.length()) { 
       System.out.println(i - j); 
      } 

      if (j > 0) { 
       j = lps[j - 1]; 
      } else { 
       i++; 
      } 
     } 
    } 

    private static int[] LPS(String pattern) { 
     int len = 0; 
     int i = 0; 
     int[] lps = new int[pattern.length()]; 

     lps[0] = 0; 
     i++; 

     while (i < pattern.length()) { 
      if (pattern.charAt(len) == pattern.charAt(i)) { 
       len++; 
       lps[i] = len; 
       i++; 
      } else if (len > 0) { 
       len = lps[len - 1]; 
      } else { 
       lps[i] = len; 
       i++; 
      } 

     } 

     return lps; 

    } 

} 

Answer 1

Ja, ich lernte KMP-Algorithmus aus der gleichen Quelle zu. Und Ihre Implementierung scheint zu 100% richtig und vollständig äquivalent zu C++ zu sein.