leetcode5.最长回文子串（马拉车算法）

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

示例 3：
输入：s = “a”
输出：“a”

示例 4：
输入：s = “ac”
输出：“a”

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) return "";
        //预处理字符串，每两个字符间加入字符'#'
        StringBuilder sb = new StringBuilder("#");
        for(int i = 0; i < s.length(); i ++){
            sb.append(s.charAt(i));
            sb.append('#');
        }
        //数组记录每个字符位置的回文长度
        int[] lenNum = new int[sb.length()];
        //记录最远回文右边界
        int rside = 0;
        //记录对应回文中心
        int rcenter = 0;
        //记录最长回文字串的中心索引
        int resindex = 0;
        //遍历字符串sb
        for(int i = 0 ; i < sb.length(); i ++){
            if(i < rside && lenNum[2 * rcenter - i] + i < rside){
                //无需中心拓展，直接更新结果
                lenNum[i] = lenNum[2 * rcenter - i];
            }else{
                if(i < rside) lenNum[i] = rside - i;
                //中心拓展
                while(i - 1 - lenNum[i] >= 0 && i + 1 + lenNum[i] < sb.length() && sb.charAt(i - 1 - lenNum[i]) == sb.charAt(i + 1 + lenNum[i])) lenNum[i] ++;
                //更新边界
                rside = lenNum[i];
                rcenter = i;
                //记录结果
                if(lenNum[i] > lenNum[resindex]) resindex = i;
            }
        }
        //处理返回结果
        StringBuilder res = new StringBuilder();
        for(int i = resindex - lenNum[resindex]; i < resindex + lenNum[resindex]; i ++){
            if(sb.charAt(i) != '#') res.append(sb.charAt(i));
        }
        return res.toString();
    }
}