字符串匹配中的計算前綴函數

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