Manacher算法，又叫“马拉车”算法，可以在时间复杂度为 的情况下求解一个字符串的最长回文子串长度的问题。
如，字符串“abc1232od”的最长回文子串是“232”

经典方法

思路：
将字符串转为数组，获取每个下标的最长回文子串。这个思路只能解决 aba 这种字符串，但是 abba 就判断不了。
可以将 abba 转为 a#b#b#a 然后判断

public class LongestPalindrome {
    static String findLongestPalindrome(String str) {
        char[] chars = new char[str.length() * 2 - 1];
        for (int i = 0; i < chars.length; i++) {
            int index = i / 2;
            chars[i] = str.charAt(index);
            if (i < chars.length - 1)
                chars[++i] = '#';
        }
        String longest = "";
        for (int i = 1; i < chars.length; i++) {
            String palindrome = getPalindrome(i, chars);
            longest = longest.length() < palindrome.length() ? palindrome : longest;
        }
        return longest;
    }
    // 获取回文子串
    private static String getPalindrome(int i, char[] chars) {
        StringBuilder palindrome = null;
        int start = i;
        int end = 0;
        if (i > chars.length - 1 - i) {
            end = chars.length - 1;
        } else {
            end = 2 * i;
        }
        for (int j = start; j <= end; j++) {
            if (palindrome == null) {
                palindrome = new StringBuilder(String.valueOf(chars[j]));
            } else {
                if (chars[j] == chars[2 * start - j]) {
                    palindrome.append(chars[j]);
                    palindrome.insert(0, chars[2 * start - j]);
                } else {
                    return palindrome.toString().replaceAll("#", "");
                }
            }
        }
        return palindrome.toString().replaceAll("#", "");
    }
    public static void main(String[] args) {
        String str1 = "abc1232od";
        System.out.println(str1 + " 的最长回文子串");
        System.out.println(findLongestPalindrome(str1));
        str1 = "ababcbaba";
        System.out.println(str1 + " 的最长回文子串");
        System.out.println(findLongestPalindrome(str1));
    }
}

结果

abc1232od 的最长回文子串
232
ababcbaba 的最长回文子串
ababcbaba

这种方法的时间复制度为

Manacher

还是和经典方法基本一致，先将字符串每两个字符中间插入 #，然后开始遍历。

Manacher 算法需要的支持：

• 回文半径数组：每个位置上回文子串的半径，如 a#1#2#1#b 的回文半径数组为 [0, 0, 1, 0, 3, 0, 1, 0, 0]，如下图

• R：最右回文右边界，就是所有的回文子串中能达到的最右边界。如 a#1#2#1#b 最右回文右边界为 8，如下图
• C：取得新的最右回文边界时中心的下标，初始为 -1，每次最右回文右边界扩张时修改。如下图

算法思路：
遍历字符串，下标为 i，做如下处理

• i > R，和经典方法保持一致
• i <= R，此时 i 一定是在 中心点 C 的右侧，i一定存在了基于 C 的对称点 i'，R一定存在了基于 C 的对称点 L，如下图：

• i' 回文半径在 [L, R] 内，i 的回文半径等于 i' 回文半径

假设 i' 的回文半径为 3，因为 [L, C] 和 [C, R] 对称，所以 [i' - 3, i' + 3] 和 [i - 3, i + 3] 对称。[i' - 3, i'] 和 [i', i' + 3] 对称，即 [i - 3, i] 和 [i, i + 3] 对称，i 的回文半径也是 3

• i' 回文半径不完全在 [L, R] 内，即i' 的回文半径超出了 L，如 i' = 3 的回文半径为 2，回文范围是 [1, 5]，超出了[L, R] 的范围 [3, 9]。 i 的回文半径等于 R-i 。证明略
• i' 回文半径等于 **i'-L**，即 **i'** 的回文左边界等于 **L**， i 的回文半径大于等于 **R-i**。前两种情况能够直接得出 i 的回文半径，这种情况需要继续验证

伪代码如下：

处理str字符串
str -> charArr
// 回文半径数组
int[] pArr = new int[charArr.length];
// 中心点
int C = -1;
// 最右边界
int R = -1;

for (int i = 0; i < charArr.length; i++) {
    if (i 在 R 的外部) {
        从 i 开始向两边暴力扩张，R 变大
    } else {
        if (i’ 回文半径在 [L,R] 内) {
            pArr[i] = pArr[i’];
        } else if (i’ 的回文半径有一部分在 [L,R] 内) {
            pArr[i] = R-i;
        } else {
            // i’ 的回文左边界等于 L
            从 R 之外的字符开始，往外扩，然后确定 pArr[i]
            如果扩张失败，R 不变，否则 R 变大
        }
    }
}

实现

public class Manacher {
    static int findLongestPalindrome(String str) {
        if (str == null || str.length() == 0) return 0;

        char[] charArr = manacherString(str);
        // 回文半径数组
        int[] pArr = new int[charArr.length];
        // 中心点
        int C = -1;
        // 最右边界
        int R = -1;

        int max = 0;

        for (int i = 0; i < charArr.length; i++) {
            // i 大于 最右回文半径 就是 1，因为没有出现过回文子串，自己构成了回文
            // i 在[L, R] 范围内就取 pArr[i']，不完全在或者 i'的回文左边界正好等于 L 就取 R - i
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            // 继续判断是否是回文子串
            // 为到达字符串边界 且 i 没有超出最右回文半径
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }

    // 给字符间加 #，这里和原先不同，会在开头和结尾都加上 #
    private static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static void main(String[] args) {
        String str1 = "abc1232od";
        System.out.println(str1 + " 的最长回文子串长度");
        System.out.println(findLongestPalindrome(str1));
        str1 = "ababcbaba";
        System.out.println(str1 + " 的最长回文子串长度");
        System.out.println(findLongestPalindrome(str1));
    }
}

结果

abc1232od 的最长回文子串长度
3
ababcbaba 的最长回文子串长度
9