leetcode 5. 最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
相关标签： 字符串、动态规划   难度： 中等

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

示例 2：
输入: "cbbd"
输出: "bb"

思路：
见Manacher算法。

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;
        char[] m = manacherString(s);
        int[] pArr = new int[m.length];
        int c = -1;
        int r = -1;
        int maxLen = -1;
        StringBuilder maxStr = new StringBuilder();
        for(int i = 0;i != m.length;i++){
            //i在r右边，直接1；否则就是pArr[cur']或R - cur + 1
            pArr[i] = i < r ? Math.min(pArr[2 * c - i], r - i + 1) : 1;
            //看能不能扩(针对压中L的情况)
            while(i - pArr[i] >= 0 && i + pArr[i] < m.length
                  && m[i - pArr[i]] == m[i + pArr[i]]){
                pArr[i]++;
            }
            if(i + pArr[i]- 1 > r){
                c = i;
                r = i + pArr[i] - 1;
            }
            if(maxLen <= pArr[i]){
                maxLen = pArr[i];
                maxStr.delete(0,maxStr.length());
                for(int j = i - pArr[i]+1;j < r;j++){
 
                    if(m[j] != '#'){
                        maxStr.append(m[j]);
                    }
                }
            }
        }
        return maxStr.toString();
    }
    private char[] manacherString(String s){
        char[] m = new char[2 * s.length() + 1];
        for(int i = 0;i < m.length;i++){
            m[i] = i % 2 == 0? '#' : s.charAt(i / 2);
        }
        return m;
    }
}