最長的迴文前綴Complextity

這個算法的複雜性是什麼？至少看起來是O（n^2）。最長的迴文前綴Complextity

// civic 
public static boolean isCharPalindrome(String test) { 
     String stripped = test.toLowerCase().replaceAll("[^0-9a-zA-Z]", ""); 
     for(int i = 0; i < stripped.length()/2; i++) { 
      if(stripped.charAt(i) != stripped.charAt(stripped.length() - 1 - i)) { 
       return false; 
      } 
     } 
     return true; 
    } 

// ILLINOISURB 
public static String longestPrefixPalindrome(String test){ 
    String max_prefix = test.substring(0,1); 
    for(int i=test.length()-1; i>=0; i--){ 
     String maxPrefix = test.substring(0, i); 
     if(isCharPalindrome(maxPrefix)){ 
      return maxPrefix; 
     } 
    } 

    return max_prefix; 
} 

public static void main(String[] args) { 
    String str = "A man, a plan, a canal, Panama!"; 
    System.out.println("isCharPalindrome:" + isCharPalindrome("A man, a plan, a canal, Panama!")); 
    System.out.println("longestPrefixPal:" + longestPrefixPalindrome("NILLINOISURB")); 
}

來源

2011-04-09 user697911

我刪除了很多垂直空間，並且註釋'// TODO自動生成的方法存根'只要您觸摸該方法，就會刪除此註釋，因爲如果您手動執行某些操作，則註釋會出錯。 – 2011-04-09 22:07:42

對我來說聽起來像[理論上的cs]（http://cstheory.stackexchange.com/） – mbx 2011-04-09 22:21:28

理論上的cs不適用於像這樣的本科層次的問題。它屬於這裏。 – 2011-04-10 07:13:40

是的。複雜度爲O（n^2），因爲isCharPalindrome的複雜度爲O（n），您從longestPrefixPalindrome調用它n次。

但是，您可以通過從最長前綴開始，然後減小測試前綴的大小來降低複雜性。如果你這樣做，一旦發現帕裏綜合徵，你可以立即退出該方法。每次你都不需要走到最後。

我確定您知道如何相應地更改longestPrefixPalindrome。

雖然看@pajton的答案。如果你仔細想想，你可以把複雜度降到O（n）。我給出的答案實際上會給你一個關於可以完成的暗示。

來源

2011-04-09 21:53:48 euphoria83

該答案被刪除，因爲在ILLINOISURB中沒有找到類似'illi'的前綴。 – 2011-04-09 22:12:01

是的。但是你是否明白如何使這個問題的複雜性O（n）？ – euphoria83 2011-04-09 22:42:26

不，但是對於任意輸入，情況並不是那麼糟糕，是嗎？對於Nillinoisurb，一個長度爲12的字符串，方法isCharPalindrom被稱爲12次，但它總是被搜索，第一個字符「N」是否與子字符串的最後一個匹配，並且這只是一次情況，並且在此有匹配的情況。現在，您可以調查平均輸入的數量，第一個字符與子字符串中的第一個字符匹配的次數。當然，迴文不是經常在現實生活中進行調查的，所以沒有經驗數據可以推論 - 我們可以推斷完全是假的話...... – 2011-04-09 23:21:54

最長的迴文前綴Complextity

回答

相關問題