文字列中の最長Palindrome部分文字列を計算する

Question

文字列中の最長palindromeサブ文字列を計算するための次のコードがあります。オンライン裁判官はO（N^2）ソリューションを受け入れますが、私のアルゴリズムはO（N^2）であるようですが、それは最初にcomplexity.`

class Ideone { 

    public static void main(String args[]) { 
     Ideone ob = new Ideone(); 
     String s = "sds"; 
     System.out.println(ob.longestPalindrome(s)); 

    } 

    public String longestPalindrome(String s) { 
     int maxlength = 1; 

     String ps = s.charAt(0) + ""; 

     if (s.length() == 1) 
      return s; 
     for (int i = 0; i < s.length() - 1; i++) { 
      int j = (s.substring(i + 1)).indexOf(s.charAt(i)) + i + 1; 
      while (j < s.length() && j > i) { 
       if (j - i + 1 > maxlength && check(s.substring(i, j + 1))) { 

        maxlength = j - i + 1; 
        ps = s.substring(i, j + 1); 

       } 
       if ((s.substring(j + 1)).indexOf(s.charAt(i)) < 0) { 
        break; 
       } 
       j = (s.substring(j + 1)).indexOf(s.charAt(i)) + j + 1; 

      } 
     } 


     return ps; 
    } 

    public boolean check(String s) { 
     int l = s.length(); 
     if (l == 1) 
      return false; 
     int t = l/2; 
     String s1, s2; 
     if (l % 2 == 0) { 
      s1 = s.substring(0, t); 
      s2 = s.substring(t); 

     } else { 
      s1 = s.substring(0, t); 
      s2 = s.substring(t + 1); 

     } 

     s2 = (new StringBuffer(s2)).reverse().toString(); 

     if (s1.compareTo(s2) == 0) 
      return true; 
     else return false; 
    } 

} 

Answer 1

に私の解決策を受け付けていませんなぜ私は知りません2つのループを見て、Stringを逆にするためにO（n）を必要とするメソッドcheck（）はO（n3）につながる可能性があります。

• String.indexOf（..）
• String.substring（..）
• String.compareTo（..）
• StringBuffer.reverse（：

  のような方法があることに注意してください..）

• String.toString（）

データしたがってNEを反復処理する必要があります約O（n）であり、一定時間ではない。

Answer 2

O（n2）以上がかかるようです。以下は動的プログラミングによるプログラムコードです。javaではありませんが、アルゴリズムとして便利です http://www.geeksforgeeks.org/longest-palindromic-substring-set-2/