Manacher 算法

/**
     * Manacher
     */
    public int countSubstrings(String s) {
        int len = s.length();
        StringBuilder sb = new StringBuilder("$#");
//        解决回文串奇数长度和偶数长度的问题，处理方式是在所有的相邻字符中间插入 '#' ，这样可以保证所有找到的回文串都是奇数长度的
        for (int i = 0; i < len; ++i) {
            sb.append(s.charAt(i)).append('#');
        }
//        设置哨兵，到了边界就一定会不相等，从而结束循环
        sb.append('%');
        len = sb.length();
//        用 radius[i] 来表示以 sb 的第 i 位为回文中心，可以拓展出的最大回文半径
        int[] radius = new int[len];
//        维护 当前最靠右的回文右端点 maxRight , 以及这个回文右端点对应的回文中心 maxMid
        int maxMid = 0;
        int maxRight = 0;
        int rs = 0;
//        剪枝
        for (int currMid = 2; currMid < len - 2; currMid++) {
//            radius[currMid] = [maxRight - currMid, radius[currMid 关于 maxMid 对称点]]
//            currMid 在当前最大回文子串内：
//              回文串的性质，关于回文中心对称的两边一样，因此当前点的回文半径至少是对称点的回文半径
//              因此 currMid 处的 回文半径 最小为 对称点的最大回文半径
//                特殊情况：currMid + 对称点的最大回文半径 > maxRight
//                此时无法取到整个对称点的最大回文半径 , 但最小可以是 currMid 到 maxRight 之间
//            currMid 不在当前最靠右的回文串内：
//              以 currMid 为中心 1 为回文半径
            radius[currMid] = currMid <= maxRight ? Math.min(maxRight - currMid + 1, radius[2 * maxMid - currMid]) : 1;
//            中心拓展
            while (sb.charAt(currMid + radius[currMid]) == sb.charAt(currMid - radius[currMid])) {
                radius[currMid]++;
            }
//            动态维护 maxMid 和 maxRight
//            当前回文右端点 = 当前中心 + 最大回文半径 - 1 > 最大回文右端点
            if (currMid + radius[currMid] - 1 > maxRight) {
                maxMid = currMid;
                maxRight = currMid + radius[currMid] - 1;
            }
//            最长回文子串的结尾一定是 '#' , 因为如果结尾是有实际意义的字符，其两端一定都是 '#'
//            中心位置如果是 '#' 则半径为偶数
//            # a # b [#] b # a #   此时回文半径为 4 , 4 >> 1 == 2
//            如果为实际意义的字符则半径为奇数向下取整
//            # a # b # [currMid] # b # a #   此时回文半径为 5 , 5 >> 1 == 2
            rs += radius[currMid] >> 1;
        }
        return rs;
    }

public String preProcess(String s) {
    int n = s.length();
    if (n == 0) {
        return "^$";
    }
    String ret = "^";
    for (int i = 0; i < n; i++)
        ret += "#" + s.charAt(i);
    ret += "#$";
    return ret;
}

// 马拉车算法
public String longestPalindrome2(String s) {
    String T = preProcess(s);
    int n = T.length();
    int[] P = new int[n];
    int C = 0, R = 0;
    for (int i = 1; i < n - 1; i++) {
        int i_mirror = 2 * C - i;
        if (R > i) {
            P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
        } else {
            P[i] = 0;// 等于 R 的情况
        }

        // 碰到之前讲的三种情况时候，需要利用中心扩展法
        while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
            P[i]++;
        }

        // 判断是否需要更新 R
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }

    }

    // 找出 P 的最大值
    int maxLen = 0;
    int centerIndex = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2; //最开始讲的求原字符串下标
    return s.substring(start, start + maxLen);
}