Leetcode #5 最长回文子串

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

示例 1：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public String longestPalindrome(String s) {
        // Manacher 算法
        // 1. 对原字符串添加分隔符，例如 "babad" 添加分隔符以后得到 "@#b#a#b#a#d#$"
        char[] A = new char[s.length() * 2 + 3];
        A[0] = '@';
        A[1] = '#';
        int t = 2;
        for(char c: s.toCharArray()) {
            A[t++] = c;
            A[t++] = '#';
        }
        A[t] = '$';
        // 辅助数组Z,记录以当前字符为中心，能够扩散的步数，最大值为最长回文串长度
        int[] Z = new int[A.length];
        // right:记录当前向右扩展的最远边界, center:right 的回文中心的索引值
        // idx: 最长回文串的中心 maxZ：Z值（长度）
        int right = 0, center = 0, idx = 0, maxZ = 0;
        for(int i = 1; i < A.length - 1; i++) {
            // mirror=2*center-i为i关于center镜像对称点，right-i为i向左走到center的距离
            // 当Z[mirror]<=right-i时，i点处和镜像点有相同的对称性，Z[i]=Z[mirror]
            // 当Z[mirror]>right-i时，此时不能再扩散了，因为最大边界为right，
            // right+1处关于center镜像点字符一定不同，Z[i]=right-i
            if(right > i) {
                Z[i] = Math.min(Z[2 * center - i], right - i);
            }
            // 中心扩散法更新Z值
            while(A[i - Z[i] - 1] == A[i + Z[i] + 1]) {
                Z[i]++;
            }
            // 记录最大Z值
            if(Z[i] > maxZ) {
                maxZ = Z[i];
                idx = i;
            }
            // 更新right和center
            if(i + Z[i] > right) {
                center = i;
                // i + Z[i] 就是right
                right = i + Z[i];
            }
        }
        return s.substring((idx - maxZ) / 2 , (idx - maxZ) / 2 + maxZ);
    }
}