LeetCode练手系列——最长回文子串

题目：最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"

输出: "bab"

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

示例 2：

输入: "cbbd"

输出: "bb"

思路和简单分析： 这道题刚开始没啥思路，本来打算暴力膜一波，但是感觉肯定无法通过... 看了网上很多解法都用了Manacher算法，能够在O(n)的情况找出最长的回文子串，虽然还看得不是很明白，但是跟着大概的思路能够AC，以后如果有时间会对代码做出优化。

思路比较简单，只需要遍历一遍数组，记录它能够组成回文字符串的半径，记录在数组p中。使用Manacher算法的思路避免奇数长和偶数长字符串的不同逻辑处理，使用不会在字符串中出现的字符做为分隔符对字符数组扩容。

上代码：

    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();
    }
}