가장 긴 palindrome 접두사 complextity

Question

이 알고리즘의 복잡도는 얼마나됩니까? 적어도 O (n^2) 이상인 것 같습니다.

// 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")); 
} 

Answer 1

예. isCharPalindrome의 복잡성은 O (n)이고 사용자는 longestPrefixPalindrome에서 n 번 호출하므로 복잡성은 O (n^2)입니다.

그러나 가장 긴 접두어로 시작한 다음 테스트 된 접두사의 크기를 줄이면 복잡성을 줄일 수 있습니다. 이렇게하면 paliendrome을 찾자 마자 즉시 방법을 종료 할 수 있습니다. 매번 끝날 때까지 갈 필요가 없습니다.

이에 따라 longestPrefixPalindrome을 변경하는 방법을 알고 계실 것입니다.

@pajton의 대답을보세요. 당신이 그것에 대해 생각한다면 당신은 복잡성을 O (n)까지 줄일 수 있습니다. 제가 준 대답은 실제로 그것에 대한 힌트를 줄 것입니다.