[5]最长回文子串

//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3305 👎 0

在题解中已有动态规划和中心扩散的方法，这题主要是学习manacher算法。
在题解的视频中也有清晰的讲解，建议跟随视频把题解代码多抄几遍，跟着debug走几遍即可了解。

有这么几个特殊参数需要提前解释
maxRight: 回文子串的最大右边界，回文子串扩散到最右的位置
center: 最大右边界对应的center
i: 当前要计算回文子串的位置
mirror: 当前位置对center的镜像位置

manacher的原理就是使用动态规划的思想，计算i的时候，可以参考mirror位置的结果。

分情况讨论：
如果i>=maxRight, 使用中心扩散的方法找最大右边界
如果i<maxRight, 又分三种情况

1. maxRight - i > dp[mirror]

根据dp[mirror]已经计算出来的长度，回文的区域没有超过maxRight，因此整个字符串对于center是对称的。
而且dp[mirror]已经扩散到最大，说明mirror-(dp[mirror]+1)和mirror+(dp[mirror]+1)两个字符肯定是不相同的，不然dp[mirror]就不是mirror为中心的最长回文子串了。
因此此时dp[i]的长度就可以直接取dp[mirror]

1. maxRight - i == dp[mirror]

此时根据图像可以看出，mirror右边界和左边界的字母是不同的，根据maxRight的对称性，i左边界的字母和mirror右边界是相同的，maxRight+1和maxRight镜像位置-1的位置一定是不同的。
那么就有可能使i的左边界和右边界向外扩散。
因此i位置的回文串长度至少是maxRight - i，实际长度还要根据该结果向外扩展。

1. maxRight - i < dp[mirror]

如果dp[mirror]的值已经超出了maxRight和center指示的回文串的范围，那么说明maxRight+1和maxRight镜像位置-1的字母一定不相同。
如果相同，maxRight的位置应该+1。
因此，根据回文串的对称性，i的左右边界一定就停在maxRight上，再无法向外扩展了。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        // 如果字符串长度小于2， 那直接就是一个回文串
        if (len < 2) {
            return s;
        }
        // 将字符串填充， 如 'abacadv' 填充为 '#a#b#a#c#a#d#v#'
        String str = addDevise(s, '#');
        int sLen = str.length();
        // maxRight 标记的是回文串可以到达的最大右边界
        int maxRight = 0;
        // center是最大右边界对应的回文中点
        int center = 0;
        // 最长回文串的起始位置
        int begin = 0;
        // 最长回文串的长度
        int maxLength = 1;
        // dp存储的是i位置为中心，最长回文串的半径
        int[] dp = new int[sLen];
        char[] chars = str.toCharArray();
        for (int i = 0; i < sLen; i++) {
            // 如果i没超过回文串的最大右边界
            if (i < maxRight) {
                // mirror是i关于center对称的位置
                int mirror = 2 * center - i;
                // dp[i]至少是dp[mirror]和(maxRight和i的距离)中的最小值
                dp[i] = Math.min(dp[mirror], maxRight - i);
            }
            // 尝试向两边扩散
            int left = i - (1 + dp[i]);
            int right = i + (1 + dp[i]);
            while (left >= 0 && right < sLen && chars[left] == chars[right]) {
                left --;
                right ++;
                dp[i] ++;
            }
            // 维护最大右边界和center
            if (i + dp[i] > maxRight) {
                maxRight = i + dp[i];
                center = i;
            }
            // 维护最长回文子串
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                begin = (i - maxLength) / 2;
            }
        }
        return s.substring(begin, begin + maxLength);
    }
    public String addDevise(String s, char ch) {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(ch);
        for (int i = 0; i < s.length(); i++) {
            stringBuilder.append(s.charAt(i));
            stringBuilder.append(ch);
        }
        return stringBuilder.toString();
    }
}