Функция префикса вычислений в соответствии со строкой

Question

Что я здесь делаю неправильно?

Код Java для вычисления префиксной функции. Два входа правильные, но последний неверен.

Вот псевдокод:

Java код:

class Main { 
// compute prefix function 
    public static void main(String[] args) { 
     String p = "422213422153342"; 
     String x = "ababbabbabbababbabb"; 
     String y = "ababaca"; 

     printOutput(p); 

     printOutput(y); 

     System.out.println();System.out.println(); 
     System.out.println("the prefix func below is wrong. I am not sure why."); 
     System.out.print("answer should be: 0 0 1 2 0 1 2 0 1 2 0 1 2 3 4 5 6 7 8"); 

     printOutput(x); 
    } 

    static void printOutput(String P){ 
     System.out.println();System.out.println(); 
     System.out.print("p[i]: "); 
     for(int i = 0; i < P.length(); i++)System.out.print(P.charAt(i) + " "); 
     System.out.println(); 
     System.out.print("Pi[i]: "); 
     compute_prefix_func(P); 
    } 
    public static void compute_prefix_func(String P){ 
     int m = P.length(); 
     int pi[] = new int[m]; 

     for(int i = 0; i < pi.length; i++){ 
      pi[i] = 0; 
     } 

     pi[0] = 0; 

     int k = 0; 

     for(int q = 2; q < m; q++){ 
      while(k > 0 && (((P.charAt(k) + "").equals(P.charAt(q) + "")) == false)){ 
       k = pi[k]; 
      } 
      if ((P.charAt(k) + "").equals(P.charAt(q) + "")){ 
       k = k + 1; 
      } 
      pi[q] = k; 
     } 

     for(int i = 0; i < pi.length; i++){ 
     System.out.print(pi[i] + " "); 
     } 
    } 
} 

Answer 1

Хорошо, давайте начнем с создания кода гораздо легче читать. Это:

if ((P.charAt(k) + "").equals(P.charAt(q) + "")) 

может быть упрощена:

if (P.charAt(k) == P.charAt(q)) 

... и вы сделали, что в нескольких местах.

Аналогично здесь:

int pi[] = new int[m]; 

for(int i = 0; i < pi.length; i++){ 
    pi[i] = 0; 
} 

pi[0] = 0; 

... Вам не нужна явная инициализация. По умолчанию значения переменных инициализируются 0. (Неясно, почему вы затем установить pi[0]снова, хотя замечу, что если P.length() равен 0, то это будет сгенерировано исключение.)

Далее следует удалить явное сравнение с false, а не только с помощью ! поэтому мы есть:

while(k > 0 && P.charAt(k) != P.charAt(q)) 

Наконец, давайте реструктурировать код немного, чтобы сделать его легче следовать, использовать более традиционные имена, и изменить int pi[] к более идиоматических int[] pi:

class Main { 
    public static void main(String[] args) { 
     String x = "ababbabbabbababbabb"; 

     int[] prefix = computePrefix(x); 

     System.out.println("Prefix series for " + x); 
     for (int p : prefix) { 
      System.out.print(p + " "); 
     } 
     System.out.println(); 
    } 

    public static int[] computePrefix(String input) { 
     int[] pi = new int[input.length()]; 

     int k = 0; 
     for(int q = 2; q < input.length(); q++) {    
      while (k > 0 && input.charAt(k) != input.charAt(q)) { 
       k = pi[k]; 
      } 
      if (input.charAt(k) == input.charAt(q)) { 
       k = k + 1; 
      } 
      pi[q] = k; 
     } 
     return pi; 
    } 
} 

Это стало намного легче следовать, ИМО.

Теперь мы можем вернуться к псевдокоду и увидеть, что он использует индексирование на основе 1 для обоих массивов и строк. Это делает жизнь немного сложной. Мы могли имитировать, что в коде, изменяя каждый доступ массива и charAt вызова просто вычесть 1.

(я извлек общие подвыражения из P[q] к переменным target внутри циклу.)

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

Это дает желаемые результаты, но это действительно уродливо. Мы можем сместить q очень легко, и удалить + 1 - 1 частей:

public static int[] computePrefix(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; 
} 

Это еще не совсем приятно, но я думаю, что это то, что вы хотите. Удостоверьтесь, что вы понимаете , почему Мне пришлось внести изменения, которые я сделал.

Answer 2

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