如何找到本身不是迴文的迴文的子串的長度？

Question

我已經寫了這段代碼，但它顯示超時超時。我怎樣才能讓這個速度更快？

import java.util.*; 
public class Palin{ 
    public static void main(String ar[]){ 
    Scanner input = new Scanner(System.in); 
    String s = input.next(); 
    for(int i = 1 ;i < s.length() ; i++){ 
     if(!(s.substring(0,i).equals(new StringBuilder(s.substring(0,i)).reverse().toString()))){ 
      System.out.print(s.substring(0,i).length()); 
     } 
    } 
    } 
} 

Answer 1

看到這個代碼 它的方法來找到

1. 各種長度
2. 最長的非迴文子
3. 最長迴文串（使用lambda表達式）

的所有可能的子

第三個提供瞭如何解決使用羊肉的問題DAS JUnit測試用例遵循底部

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 
import java.util.stream.Collector; 
import java.util.stream.Collectors; 

public class MyStrings { 

    private String s; 
    public MyStrings(String s) { 
     super(); 
     if(s==null||s.trim().length()==0) s=""; 
     this.s = s; 
    } 

    public Set<String> getAllSubStrings() { 

     Set<String> list=new HashSet(); 
     for (int i=0, m=s.length()-1,n=m+1 ;i<=m;i++) { 
      for (int j=i+1;j<=n;j++) 
       list.add(s.substring(i, j)); 
     } 
     return list; 
    } 

    public String getLongestPalindromeSubstr(boolean excludeOriginal) { 
     Set<String> subs = this.getAllSubStrings(); 

     //if original string to be not considered then remove it from the set 
     if (excludeOriginal) 
      subs.remove(s); 

     if(s.isEmpty()) 
      return ""; 

     return subs.stream() 
     .filter(s-> new StringBuilder(s).reverse().toString().equals(s)) 
     .sorted((s1,s2)-> {//sorted in descending order of string length 
      if (s1.length()<s2.length()) return 1; 
      if (s1.length()==s2.length()) return 0; 
      return -1; 
     }) 
     .findFirst() 
     .get(); //return the biggest palindrome substring 

     /* 
     Set<String> subs =this.getAllSubStrings(); 
     System.out.println(subs); 

     List<String> palindromSubStrings = subs.stream() 
     .filter(s-> new StringBuilder(s).reverse().toString().equals(s)) 
     .sorted((s1,s2)-> { 
      //System.out.println("comparing ["+s1+"],["+s2+"]"); 
      if (s1.length()<s2.length()) return 1; 
      if (s1.length()==s2.length()) return 0; 
      return -1; 
     }) //sorted in descending order 
     .collect(Collectors.toList()); 

     System.out.println("palindromSubStrings"+palindromSubStrings); 
     return palindromSubStrings.stream(). 
     findFirst().get(); 
     */ 

    } 
    public String getLongestNonPalindromeSubstr(boolean excludeOriginal) { 
     Set<String> subs =this.getAllSubStrings(); 
     Set<String> nonPalindromes = new HashSet(); 
     for (String str:subs) { 
      if (! new StringBuilder(str).reverse().toString().equals(str)) 
       nonPalindromes.add(str); //remove 
     } 
     //if original string to be not considered then remove it from the set 
     if (excludeOriginal) 
      nonPalindromes.remove(s); 
     System.out.println("Non Palindromes with parent excluded="+excludeOriginal+" is "+nonPalindromes); 
     if (nonPalindromes.isEmpty())return ""; 
     String longest=""; 
     for (String str:nonPalindromes) 
      if(str.length()>=longest.length()) longest=str; 

     return longest;//one of the longest if the set has abc, def, ghi then any one will be returned 
    } 


} 

------ JUnit測試用例方法---------

@Test 
    public void testAllPossibleSubStrings() { 
     Map<String,String[]> d = new LinkedHashMap(); //data 
     d.put("a", new String[]{"a"}); 
     d.put("aa", new String[]{"a","aa"}); 
     d.put("ab", new String[]{"a","b","ab"}); 
     d.put("abc", new String[]{"a","ab","abc","b","bc"}); 
     d.put("abcd", new String[]{"a","ab","abc","abcd","b","bc","bcd","c","cd"}); 

     d.keySet().forEach(k-> { 
      MyStrings s = new MyStrings(k); 
      Set<String> allSubStrings = s.getAllSubStrings(); 
      //System.out.println(k+"->"+allSubStrings); 
      assertTrue(allSubStrings.containsAll(Arrays.asList(d.get(k)))); 
     }); 
    } 

    @Test 
    public void longestPalindromeSubstring() { 
     System.out.println("largestPalindromeSubstring"); 
     Map<String,Integer> d = new LinkedHashMap(); //data 
     d.put("a", 1); 
     d.put("ab", 1); 
     d.put("abc", 1); 
     d.put("abcc", 2); 
     d.put("abcdcb", 5);//"bcdcb"); 
     d.put("abcbabcd",5); 
     d.put("abc-cbad-dabc-aa",11); 

     d.keySet().forEach(k-> { 
      System.out.println("==========="+k+"==================="); 
      MyStrings s = new MyStrings(k); 
      boolean excludeOriginal = false;    
      String longestPalin = s.getLongestPalindromeSubstr(excludeOriginal); 
      System.out.println("biggestPalinSubstr("+k+")="+longestPalin); 
      assertEquals(longestPalin.length(),(int)d.get(k)); 
     });  
    } 

    @Test 
    public void longestNonPalindromeSubString() { 
     System.out.println("getLongestNonPalindromeSubString"); 
     Map<String,Integer> d = new LinkedHashMap(); //data 
     d.put("a", 0); 
     d.put("ab", 2); 
     d.put("abc", 3); 
     d.put("abcc", 4); 
     d.put("abcdcb", 6);//"bcdcb"); 
     d.put("abcbabcd",8); 
     d.put("abc-cbad-dabc-aa",16); 

     d.keySet().forEach(k-> { 
      System.out.println("==========="+k+"==================="); 
      MyStrings s = new MyStrings(k); 
      boolean excludeOriginal = false; 
      String longestNonPalin = s.getLongestNonPalindromeSubstr(excludeOriginal); 
      System.out.println("longestNonPalin ("+k+")="+longestNonPalin); 
      assertEquals(longestNonPalin.length(),(int)d.get(k)); 
     });  
    } 
    @Test 
    public void longestNonPalindromeSubString2() { 
     System.out.println("getLongestNonPalindromeSubString"); 
     Map<String,Integer> d = new LinkedHashMap(); //data 
     d.put("a", 0); 
     d.put("ab", 0); //a,b are palindromes ab is excluded return 
     d.put("abc", 2); //a,b,c,abc are excluded 
     d.put("abcc", 3); 
     d.put("abcdcb", 5);//"bcdcb"); 
     d.put("abcbabcd",7); 
     d.put("abc-cbad-dabc-aa",15); 

     d.keySet().forEach(k-> { 
      System.out.println("==========="+k+"==================="); 
      MyStrings s = new MyStrings(k); 
      boolean excludeOriginal = true; 
      String longestNonPalin = s.getLongestNonPalindromeSubstr(excludeOriginal); 
      System.out.println("longestNonPalin2 ("+k+")="+longestNonPalin); 
      assertEquals((int)d.get(k),longestNonPalin.length()); 
     });  
    } 

Answer 2

這看起來好像沒什麼問題。

import java.util.*; 
public class StackOverFlow{ 
    public static void main(String ar[]){ 
    Scanner input = new Scanner(System.in); 
    String s = input.next(); 
    int length = 0; 
    for(int i = 1 ;i <= s.length() ; i++){ 
     if(!(s.substring(0,i).equals(new StringBuilder(s.substring(0,i)).reverse().toString()))){ 
     length = s.substring(0,i).length(); 
     } 
    } 
    System.out.println(length); 
    } 
}