字符串匹配中的计算前缀函数

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

现在更容易遵循IMO。

我们现在可以回头看看伪代码，并且看到它似乎在使用基于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; 
}