题解 | #最长回文子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */


    // 算法要求高的公司，在问最长回文子串的时候，会要求你写出O(n)的解法，此时就需要你掌握马拉车算法
    // 马拉车算法主要解决两件事情： 1.单个回文和两个回文讨论   2.记忆半径来减少重复计算
    // 1. 单个回文和两个回文讨论，通过对字符串添加"#"保证不需要讨论
    // 2. 记忆半径：
    //       2.1 半径数组 radius[]
    //       2.2 core.   c
    //       2.3 右边界.  r
    // 3. 如何计算：
    //       3.1  边界 > 当前index， 以c为中心的对称半径数组, 需要限制一下R的边界，表现出的代码就是Math.min()
    //       3.2  边界 <= 当前index, 默认为1
    //       3.3  两边同时延伸，计算半径
    //       3.4  更新c和r
    public int getLongestPalindrome (String A) {
        // write code here
        return manacher(A);
    }

    public static char[] manacherString(String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            sb.append("#");
            sb.append(str.charAt(i));
        }
        sb.append("#");
        return sb.toString().toCharArray();
    }

    public static int manacher(String str) {
        if (str == null || str.length() < 1) {
            return 0;
        }
        // 对字符串进行extend
        char[] charArr = manacherString(str);
        // 构建数组半径
        int[] radius = new int[charArr.length];
        int R = -1;
        int c = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < radius.length; i++) {
            // 以c为核，对应的另外一边的半径值，并通过R来进行约束
            radius[i] = R > i ? Math.min(radius[2 * c - i], R - i + 1) : 1;
            // 延伸
            while (i + radius[i] < charArr.length && i - radius[i] > -1) {
                if (charArr[i - radius[i]] == charArr[i + radius[i]]) {
                    radius[i]++;
                } else {
                    break;
                }
            }
            // 更新R和c
            if (i + radius[i] > R) {
                R = i + radius[i] - 1;
                c = i;
            }
            max = Math.max(max, radius[i]);
        }
        return max - 1;
    }
}

时间复杂度O(n)