KMP 패턴 일치 알고리즘의 구현이 맞습니까?

Question

나는이 링크에서 KMP에 관해 읽고있다 : (http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/).

나는 각각의 링크에서 주어진 것 이외의 KMP를 구현했으며 올바른 대답도 제공한다. 누군가 KMP의 이러한 구현이 옳은지 또는 틀린 지 말해 줄 수 있는가? 틀린 경우에, 친절하게 동일을 설명하십시오.

다음은 나에 의해 구현 :

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

예, 저도 같은 소스에서 KMP 알고리즘을 배웠습니다. 그리고 당신의 구현은 C++의 100 % 맞고 완전한 동등한 것 같습니다.