Java: KMP согласовани алгоритм

Question

Я пытаюсь реализовать выше алгоритм в Java. Однако я получаю исключение из-за пределов, и я не знаю, как это исправить.

Я просто переводил psuedocode довольно много строк за строкой.

Вот код:

public static int[] computePrefixFunction(String input) 
    { 
     int[] pi = new int[input.length()]; 
     int k = 0; 
     for (int q = 1; q < input.length(); q++) { 
      char target = input.charAt(q); 
     while (k > 0 && input.charAt(k) != target) k = pi[k - 1]; 
     if (input.charAt(k) == target) k++; 
     pi[q] = k; 
    } 
    return pi; 
} 

public static Queue<Integer> KMPMatcher(String T, String P) 
{ 
    int n = T.length(); 
    int m = P.length(); 
    int[] pi = computePrefixFunction(P); 
    int q = 0; 
    Queue<Integer> Q = new LinkedList<>(); 
    for(int i = 0; i < n; i++) 
    { 
     while(q > 0 && P.charAt(q+1) != T.charAt(i)) 
      q = pi[q]; 
     if(P.charAt(q+1) == T.charAt(i)) 
      q = q + 1; 
     if(q == m-1) // you match it when q reaches size of pattern -1. :) 
     { 
      Q.add(i-m+1); // Change it as well. 
      q = pi[q]; 
     }  
    } 
    return Q; 
} 

public static void main(String[] args) { 
    System.out.println(KMPMatcher("bdacabdacb","bda")); 
} 

Edit: Я обновил код с реализацией Piyush ниже которого скорректированное некоторые из моих проблем. Однако есть и другая проблема.

Я испытал KMPMatcher используя эти:

1) System.out.println(KMPMatcher("bacabab","bab")); // returned [2,4]

2) System.out.println(KMPMatcher("bdacabdacb","bab")); // returned [3]

номер 1 должен возвращать только 4 и номер 2 должен возвращать только пустой список. Почему это происходит? Я пытаюсь нарисовать след с этими входами и сравнить его с psuedocode. Я думаю, что это связано с индексацией в if(q==m-1) (потому что это не сравнение правильной вещи по сравнению с версией psuedocode?), И я не уверен, как ее исправить. Любая помощь, пожалуйста?

Answer 1

Проблема в заявке if. Это не должно быть if (q == m-1).

public static int[] computePrefixFunction(String input) 
    { 
     int[] pi = new int[input.length()]; 
     int k = 0; 
     for (int q = 1; q < input.length(); q++) { 
      char target = input.charAt(q); 
     while (k > 0 && input.charAt(k) != target) k = pi[k - 1]; 
     if (input.charAt(k) == target) k++; 
     pi[q] = k; 
    } 
    return pi; 
} 

    public static Queue<Integer> KMPMatcher(String T, String P) 
{ 
    int n = T.length(); 
    int m = P.length(); 
    int[] pi = computePrefixFunction(P); 
    int q = 0; 
    Queue<Integer> Q = new LinkedList<>(); 
    for(int i = 0; i < n; i++) 
    { 
     while(q > 0 && P.charAt(q) != T.charAt(i)) 
      q = pi[q-1]; 
     if(P.charAt(q) == T.charAt(i)) 
      q++; 
     { 
      Q.add(i-q+1); // Change it. 
      q = pi[q-1]; 
     }  
    } 
    return Q; 
} 

public static void main(String[] args) { 
    System.out.println(KMPMatcher("bdacabdacb","bda")); 
}