題目：最長回文子串

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為1000。

示例 1：

輸入: "babad"

輸出: "bab"

注意: "aba"也是一個有效答案。

示例 2：

輸入: "cbbd"

輸出: "bb"

思路和簡單分析： 這道題剛開始沒啥思路，本來打算暴力膜一波，但是感覺肯定無法通過... 看了網(wǎng)上很多解法都用了Manacher算法，能夠在O(n)的情況找出最長的回文子串，雖然還看得不是很明白，但是跟著大概的思路能夠AC，以后如果有時間會對代碼做出優(yōu)化。

思路比較簡單，只需要遍歷一遍數(shù)組，記錄它能夠組成回文字符串的半徑，記錄在數(shù)組p中。使用Manacher算法的思路避免奇數(shù)長和偶數(shù)長字符串的不同邏輯處理，使用不會在字符串中出現(xiàn)的字符做為分隔符對字符數(shù)組擴(kuò)容。

上代碼：

    public String longestPalindrome(String s) {
        char[] c = s.toCharArray();
        
        //分隔字符
        StringBuffer sb = new StringBuffer();
        sb.append("#");
        for (int i = 0;i<c.length;i++){
            sb.append(c[i]);
            sb.append("#");
        }

        int[] p = new int[sb.length()];
        int max = 0;
        int id = 0;
        
        //計算回文串長度
        for(int i = 0;i<sb.length();i++){

            int count = 1;
            p[i] = 1;
            while (i-count>=0  && i+count<sb.length() && sb.charAt(i-count)==sb.charAt(i+count)){
                p[i]++;
                count++;
            }

            if(p[i]>max){
                max = p[i];
                id = i;
            }
        }

        int r = max-1;
        int start = id-r;
        int end = id+r;

        StringBuffer res = new StringBuffer();
        
        //拼接最長回文串
        for (int i = start;i<=end;i++){
            if (sb.charAt(i)!='#'){
                res.append(sb.charAt(i));
            }
        }

        return res.toString();
    }
}