5. 最长回文子串

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

输入: "cbbd"
输出: "bb"

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        // 预处理字符串，避免奇偶问题
        String str = preProcess(s);
        int id = 0;
        //mx 代表以 id 为中心的最长回文的右边界
        int mx = 0;
        //用来保存最长回文子串的中心
        int maxId = 0;
        //用来保存最长回文子串的半径
        int maxSpan = 0;
        //辅助数组p[i]代表对应字符串str中下标为i为中心的最长子串的半径
        int[] p = new int[str.length()];
        //跳过$符从#开始
        for (int i = 1; i < str.length(); i++) {
            //可能很多人不明白2 * id - i表示的是以id为中心最长子串i对应的另一个对标点，也就是
            //上图的j;如上图因为i，j是关于id的对称点，并且还是当前以id为中心最长子串的子集，所以
            //p[2 * id - i]的值也就是p[i]的值，但是因为mx > i，所以mx-i也是一个以i为中心的子串半径
            //i子串半径不能大于mx-i所以用一个min函数比较。
            p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 1;
            //探索当前p[i]半径的边界
            while ((i + p[i]) < str.length() && str.charAt(i + p[i]) == str.charAt(i - p[i])) {
                p[i]++;
            }
            //如果右边界值大于mx，那要更新mx的值和id值
            if (i + p[i] > mx) {
                mx = p[i] + i;
                id = i;
            }
            //保存最新的最长子串半径和中点
            if (p[i] > maxSpan) {
                maxSpan = p[i];
                maxId = i;
            }
        }
        //去除占位符所以要除以2
        return s.substring((maxId - maxSpan) / 2, (maxSpan + maxId) / 2 - 1);
    }

    private String preProcess(String s) {
        // 如ABC,变为$#A#B#C#
        StringBuilder sb = new StringBuilder();
        sb.append("$");
        for (int i = 0; i < s.length(); i++) {
            sb.append("#");
            sb.append(s.charAt(i));
        }
        sb.append("#");
        return sb.toString();
    }
}