leet code 5. 最长回文子串

5. 最长回文子串

题目描述

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad" 输出："bab"

解释："aba" 同样是符合题意的答案。

示例 2： 输入：s = "cbbd" 输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

题目解析--Manacher算法

重构字符串

• 以示例1为例，字符串 s = "babad"
• 可被重构为 s = "!#b#a#b#a#d#@"
• 为什么重构？

• 为了保证被处理的字符串的长度一定是偶数

计算字符对应回文半径

重构后的字符 s = "!#b#a#b#a#d#@"

! # b # a # b # a # d # @    : 可以计算该字符串的回文半径
0 0 1 0 3

计算到字符 a 的时候，可以得到其回文半径长为 3
! # b # a # b # a # d # @    
0 0 1 0 3 ^

计算  a 下一个字符 # 的回文半径的时候可以利用之前的计算——如下图

• 以 a 为中心点，左右两边的字符是对称的，左边字符的回文半径已经计算得出
• 对称点的回文半径 = min(左边对称点的回文半径，右边界减去当前索引位置)

• 因为不能超过右边界

计算最终结果

• 1 、2 步可以得到回文中心点，和回文半径
• 再次遍历字符串得到最长回文子串

show code

class Solution {
    public String longestPalindrome(String s) {
        // 第一步，重新构造 字符串 s，使其变成 偶数长度
        StringBuilder build = new StringBuilder("!#");
        int len = s.length();
        for(int i = 0;i < len;i++) {
            build.append(s.charAt(i));
            build.append('#');
            if(i == len - 1) {
                build.append('@');
            }
        }
        int n = build.length();
        // 半径数组.
        int[] radious = new int[n];
        int c = 0,r = 0;
        // 从第三个字符开始遍历.
        for(int i = 2;i < n - 2;i++) {
            if(i < r) {
                // r ：当前计算出的最长回文半径，这里的最长是指 r 对应索引的大小
                radious[i] = Math.min(r - i, radious[2*c - i]);
            }

            while(build.charAt(i - radious[i]) == build.charAt(i + radious[i])) {
                radious[i]++;
            }

            if(i + radious[i] > r) {
                r = i + radious[i];
                c = i;
            }
        }
        r = 0;
        int max = 0;
        for(int i = 2;i < n - 2;i++) {
            if(radious[i] > r) {
                r = radious[i];
                max = i;
            }
        }
        StringBuilder ans = new StringBuilder();
        for(int i = max - r + 1;i < max + r;i++) {
            if(build.charAt(i) != '#') {
                ans.append(build.charAt(i));
            }
        }
        return ans.toString();
    }
}