马拉车算法

针对最长回文子串相关的问题，马拉车算法应该是比较通用的解法，今天我们就来具体看看这个算法。

简介

马拉车算法(Manacher‘s Algorithm)是用来查找一个字符串的最长回文子串的线性方法，由一个叫 Manacher 的人在1975年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性。

这个算法最厉害的地方是在于能够在线性时间内解决问题。一般我们解决最长回文子串，不可避免都要进行回溯之类的操作，那么时间复杂度一定是大于线性的。

而马拉车算法的主要思路是维护一个跟原字符串 str 长度一样的数组 lens，lens[i] 表示以 str[i] 为中点的回串其中一边的长度。

在这里，有的人把中点算进去，有的人记录两边的长度，其实都是一样的。我在这里是只记录一边的长度，不包括中点。比如CDCDE：

1 2	str: [C, D, C, D, E] lens: [0, 1, 1, 0, 0]

那么 lens 里最大的自然就对应最长回串的中点了。所以这个算法的核心就是如何快速计算 lens。

具体思路

预处理

回文有奇偶长度两种情况，通过补充间隔符可以将这两种情况化简为奇数长度。

比如：

ABA补充为^#A#B#A#$，中点还是 B。
ABBA补充为^#A#B#B#A#$，中点为 #，最后可以去掉。

针对间隔符，首先要确保在字符串中不会出现，这里我是确保字符串中不会出现^、#、$。

原字符串中每一个字符都会被#包围，这样就确保现在的字符串长度一定是奇数。

至于在开头增加^，在结尾增加$，这样是为了确保从任意一个位置开始检查回文时，一定会遇到不一样的时候，从而退出循环。而且也方便我们计算原字符的下标，直接除以2即可。

写法是：

String str = "cbcbccde";
char[] T = new char[str.length() * 2 + 3];
T[0] = '^';
T[1] = '#';
T[T.length - 1] = '$';
for (int i = 0; i < str.length(); i++) {
    char charStr = str.charAt(i);
    T[2 * i + 2] = charStr;
    T[2 * i + 3] = '#';
}

计算长度数组

这就是算法的关键了，它充分利用了回文串的对称性。

我们用 C 表示回文串的中心，用 R 表示回文串的右边半径。所以 R = C + P[ i ] 。C 和 R 所对应的回文串是当前循环中 R 最靠右的回文串。用 i_mirror 表示当前需要求的第 i 个字符关于 C 对应的下标。

让我们考虑求 P [ i ] 的时候：

我们可以利用回文串 C 的对称性。i 关于 C 的对称点是 i_mirror ，P [ i_mirror ] = 3，所以 P [ i ] 也等于 3 。

但需要考虑特殊情况：

P [ i_mirror ] + i >= R

如下图：

当我们要求 P [ i ] 的时候，P [ mirror ] = 7，而此时 P [ i ] 并不等于 7 ，为什么呢，因为我们从 i 开始往后数 7 个，等于 22 ，已经超过了最右的 R ，此时不能利用对称性了，但我们一定可以扩展到 R 的，所以 P [ i ] 至少等于 R - i = 20 - 15 = 5，会不会更大呢，我们只需要比较 T [ R+1 ] 和 T [ R+1 ]关于 i 的对称点就行了，就像中心扩展法一样一个个扩展。

i_mirror - P [ i_mirror ] == 0

如下图：

此时P [ i_mirror ] = 1，但是 P [ i ] 赋值成 1 是不正确的，出现这种情况的原因是 P [ i_mirror ] 在扩展的时候首先是 “#” == “#” ，之后遇到了 “^”和另一个字符比较，也就是到了边界，才终止循环的。而 P [ i ] 并没有遇到边界，所以我们可以继续通过中心扩展法一步一步向两边扩展就行了。

C 和 R 的更新

既然知道如何计算长度数组了，那最关键的 C 和 R 到底什么时候需要更新呢？

i + P [ i ] > R时，也就是当求出的 P [ i ] 的右边界大于当前的 R 时，我们就需要更新 C 和 R 为当前的回文串了。因为我们必须保证 i 在 R 里面，所以一旦有更右边的 R 就要更新 R。

最终写法

假设我们要写一个方法，传入参数是原字符串s，返回值是各个字符对应的最长回文子串长度数组，那么具体方法就是：

public int[] calSubstrings(String s) {
    if (s.length() == 0) {
        return new int[0];
    }
    // 存放新的内容
    char[] content = new char[s.length() * 2 + 3];
    // 开头用^
    content[0] = '^';
    // s中的每一个字符要用#包围
    content[1] = '#';
    for (int i = 0; i < s.length(); i++) {
        content[i * 2 + 2] = s.charAt(i);
        content[i * 2 + 3] = '#';
    }
    // 结尾用$
    content[content.length - 1] = '$';

    // 当前的回文串中心下标
    int center = 0;
    // 当前的回文串右边界
    int right = 0;
    // 存储以每一个位置为中心，所能获得的最长回文子串的长度
    int[] maxLength = new int[content.length];
    // 首尾两个字符没有必要计算
    for (int index = 1; index < content.length - 1; index++) {
        // 如果当前求解的位置，在右边界以内
        if (index < right) {
            // 则其最长回文子串的长度，至少为：
            maxLength[index] = Math.min(
                    // 对称center的位置上的
                    maxLength[center * 2 - index],
                    // 或者当前位置到右边界的距离
                    right - index
            );
        }

        // 正常求解，向左右扩展
        while (content[index + (maxLength[index] + 1)] ==
                content[index - (maxLength[index] + 1)]) {
            maxLength[index]++;
        }

        // 如果当前index对应的右边界，比现有的right大
        if (index + maxLength[index] > right) {
            // 更新右边界和中心
            right = index + maxLength[index];
            center = index;
        }
    }

    // 最终的结果
    int[] result = new int[s.length()];
    for (int i = 0; i < s.length(); i++) {
        result[i] = maxLength[i * 2 + 2];
    }
    return result;
}