马拉车算法

Manacher's Algorithm，中文名叫马拉车算法，是一位名叫Manacher的人在1975年提出的一种算法，解决的问题是求最长回文子串，神奇之处在于将算法的时间复杂度精进到了O(N)，下面我们来详细介绍下这个算法的思路。

01 算法由来

在求解最长回文子串的问题时，一般的思路是以当前字符为中心，向其左右两边扩展寻找回文，但是这种解法的时间复杂度是O(N^2)，那么能不能将时间复杂度再降低一点？做到线性？马拉车算法就完美地解决了这个问题。

02 预处理

回文字符串以其长度来分，可以分为奇回文（其长度为奇数）、偶回文（其长度为偶数），一般情况下需要分两种情况来寻找回文，马拉车算法为了简化这一步，对原始字符串进行了处理，在每一个字符的左右两边都加上特殊字符（肯定不存在于原字符串中的字符），让字符串变成一个奇回文。例如：

原字符串：abba，长度为4
预处理后：#a#b#b#a#，长度为9

原字符串：aba，长度为3
预处理后：#a#b#a#，长度为7

03 计算最长回文子串长度

以字符串"cabbaf"为例，将预处理后的新字符串"#c#a#b#b#a#f#"变成一个字符数组arr，定义一个辅助数组int[] p，p的长度与arr等长，p[i]表示以arr[i]字符为中心的最长回文半径，p[i]=1表示只有arr[i]字符本身是回文子串。

i       0 1 2 3 4 5 6 7 8 9 10 11 12 13
arr[i]  $ # c # a # b # b # a  #  f  #
p[i]      1 2 1 2 1 2 5 2 1 2  1  2  1

在补上字符'$'后，p[7]=5，用i减去最长半径，7-5=2，而理想的结果应该是1，那就再除以2吧，这样就能得到1了。而奇回文"aba"在用i减去最长半径后得到的是0，除以2后还是0，可以完美解决下标越界的问题。

结论：最长回文子串的起始索引int index = (i - p[i])/2。

05 计算p数组

在第三步和第四步中我们都用到了一个关键对象p数组，存放的是最长回文子串半径，那么它是怎么来的呢？
还是以上面的例子配合着看，

public static String Manacher(String s) {
    if (s.length() < 2) {
        return s;
    }
    // 第一步：预处理，将原字符串转换为新字符串
    String t = "$";
    for (int i=0; i.length(); i++) {
        t += "#" + s.charAt(i);
    }
    // 尾部再加上字符@，变为奇数长度字符串
    t += "#@";
    // 第二步：计算数组p、起始索引、最长回文半径
    int n = t.length();
    // p数组
    int[] p = new int[n];
    int id = 0, mx = 0;
    // 最长回文子串的长度
    int maxLength = -1;
    // 最长回文子串的中心位置索引
    int index = 0;
    for (int j=1; j-1; j++) {
        // 参看前文第五部分
        p[j] = mx > j ? Math.min(p[2*id-j], mx-j) : 1;
        // 向左右两边延伸，扩展右边界
        while (t.charAt(j+p[j]) == t.charAt(j-p[j])) {
            p[j]++;
        }
        // 如果回文子串的右边界超过了mx，则需要更新mx和id的值
        if (mx < p[j] + j) {
            mx = p[j] + j;
            id = j;
        }
        // 如果回文子串的长度大于maxLength，则更新maxLength和index的值
        if (maxLength < p[j] - 1) {
            // 参看前文第三部分
            maxLength = p[j] - 1;
            index = j;
        }
    }
    // 第三步：截取字符串，输出结果
    // 起始索引的计算参看前文第四部分
    int start = (index-maxLength)/2;
    return s.substring(start, start + maxLength);
}