学步园

题目：

Given a string S,
find the longest palindromic substring in S.
You may assume that the maximum length of S is
1000, and there exists one unique longest palindromic substring.

思路：

1000之内暴力可以解决。关键就是，如何考虑aa的情况。aba这种情况，挨个字母探索就行。问题就是偶数对称的情况。

我寻找了一个办法能够将奇数和偶数的统一当做偶数处理。即：将所有字母的两边都加上一个填充字符，包括第一个字符前面和最后一个字符后面，

都填充字符。这样，S也就变成2000的数量级了，到了最后别忘了去掉填充的字符即可。暴力搜索依旧是可以的。

AC代码：

public class Longest_Palindromic_Substring {
    private int maxLen = -1;
    private int start = -1;
    private int end = -1;

    private int findLongest(char[] ss, int idx){
        int i=1;
        for(;idx+i<ss.length && idx-i>=0 && ss[idx+i]==ss[idx-i];i++);
        return i-1;
    }
    public String longestPalindrome(String s) {
        char[] ss = s.toCharArray();
        StringBuffer sb = new StringBuffer("");
        for(char c:ss){
            sb.append(' ');
            sb.append(c);
        }
        sb.append(' ');

        char[] bb = sb.toString().toCharArray();

        for(int i=1;i<bb.length-1;i++){
            int tmp = findLongest(bb,i);
            if(maxLen<tmp){
                maxLen=tmp;
                start = i-maxLen;
                end = i+maxLen;
            }
        }
        if(start==-1){
            start = 0;
            end = 0;
        }
        String sbb = sb.toString().substring(start,end+1);
        return sbb.replaceAll(" ","");
    }


    public static void main(String[] args){
        Longest_Palindromic_Substring longest_palindromic_substring = new Longest_Palindromic_Substring();
        System.out.println(longest_palindromic_substring.longestPalindrome("a"));
    }
}