简介

了解马拉车算法的作用前，先要知道回文字符串的概念。回文字符串是指无论正着读还是反着读，结果都是一样的字符串。例如 aba、abba 都是回文字符串。

马拉车算法就是用来求一个字符串中的最长回文子串。例如 LeetCode 的第五题“最长回文子串”。

算法思路

马拉车算法的思想和中心扩展算法类似，也是求每个中心点向外扩展得到的最长回文子串长度，所有中心点中最长的回文子串就是要求的结果。

但是中心扩展算法的时间复杂度是 O(n^2)，而马拉车算法对其进行了改进，主要是消除了奇偶回文以及充分利用前面的回文子串信息，把时间复杂度降低到了线性级别。

算法步骤

一、预处理：在字符间插入特殊字符

回文字符串按照长度的奇偶性，可以分为奇回文和偶回文，一般情况下需要分这两种情况来寻找回文。

马拉车算法进行了简化，在每一个字符的左右两边都加上一个特殊字符（该字符不同于在字符串的任一字符），保证回文子串中只存在奇回文。例如：

1
2
3

原字符串：aba（长度为 3，为奇回文）

预处理后：#a#b#a#（长度为 7，还是奇回文）

1
2
3

原字符串：abba（长度为 4，为偶回文）

预处理后：#a#b#b#a#（长度为 9，变成了奇回文）

可以看到，加入了特殊字符后，保证了回文子串中只存在奇回文。

为了保证之后在进行中心扩散时不会超出范围，在加入了特殊字符后，继续在新的字符串两边各添加一个字符，该字符要不同于特殊字符和原字符串中的字符。例如之前插入的特殊字符为 “#”，那么可以在两边添加 “$” 和 “@”（注意：两边添加的字符也不能相同）。

二、计算半径数组 p

定义一个辅助数组 p，该数组的长度和预处理后新字符串的长度一致。假设新字符串为 t，p[i] 表示以 t[i] 字符为中心的最长回文半径 。例如对于字符串 “kabac”，对应的 p[i] 如下：

i	0	1	2	3	4	5	6	7	8	9	10
t[i]	#	k	#	a	#	b	#	a	#	c	#
p[i]	1	2	1	2	1	4	1	2	1	2	1

p[i] - 1 的值代表了以 s[i]（s 为原字符串）为中心的最长回文子串的长度。

看完 p[i] 的含义，不难知道只要求出了各个 p[i] 的值，也就得到了最长回文子串的长度和其中心点，也就知道结果了。

所以重点和难点就是如果求数组 p：

求数组 p

在计算数组 p 的整个过程，一直在更新着两个重要的变量：

mx：现有的所有回文子串中，最大的右边界（回文子串不包括 mx）
id：上述 mx 对应回文子串的中心点

在更新 p[i] 时，根据 mx 和 i 的大小，分为两种情况：

mx > i

这时 p[i] 的计算公式为：p[i] = Math.min(p[2 * id - i], mx - i)

这条公式是怎么来的呢？

首先理解下 2 * id - i 代表什么，它是 i 关于 id 的对称点。验证如下：

假设 j 为 i 关于 id 的对称点，那么 (i + j) / 2 = id，求解公式地 j = 2 * id - i，也就是刚才的值。

这里充分利用了之前求得的最右回文子串，由于 j 和 i 是对称的，并且 p[j] 已知，所以在以 id 为中心的回文子串范围内（小于 mx），p[i] 可以先赋为对称范围内的 p[j] 最大值，而 mx - i 是为了保证不超出对称范围。

例如下列子串（先省略 #）：

可以看出 p[j] = 3，但是最边的 d 是不属于对称范围内的，而 p[i] 的值应该是 2，mx - i 就起到了限制最大的 p[j] 不超出对称范围的作用。例如这里的 mx - i 的值为 2，就保证了 p[i] 在对称范围内只能更新到 2。

到这里就解释完公式了，但是 p[i] 的值还没求完，上面得到的 p[i] 只是利用前面结果得到的暂时值。还要继续以 i 为中心向两边扩散，直到两边的值不等，得到的才是最终的 p[i]。

mx <= i

这种情况就简单得多了，首先初始化 p[i] 为 1，然后继续以 i 为中心向两边扩散，直到两边的值不等，得到最终的 p[i]。

三、得到最长回文子串

在更新 p[i] 的过程中，还要借助两个变量暂存最长回文子串：

maxLen：最长回文子串的长度
maxIndex：最长回文子串的中心位置索引

如果发现了更长的回文子串，就更新这两个变量：

if (p[i] - 1 > maxLen) {
    maxLen = p[i] - 1;
    maxIndex = i;
}

前面说过了，p[i] - 1 就代表了以 s[i] 为中心的最长回文子串长度。

最后通过这两个变量求出最长回文子串的起始索引：(maxIndex - maxLen) / 2

也就得到了最终的结果：s.substring(start, start + maxLen)

完整代码实现

/**
 * 马拉车算法：找到字符串 s 中的最长回文子串
 */
private String manacher(String s) {
    if (s.length() < 2) {
        return s;
    }

    // 第一步：预处理，将原字符串转换为新的字符串
    StringBuilder builder = new StringBuilder();
    builder.append("$");
    for (int i = 0; i < s.length(); i++) {
        builder.append("#");
        builder.append(s.charAt(i));
    }
    builder.append("#@");
    String t = builder.toString();

    // 第二步：得到数组 p
    // p[i] 为 s[i] 的回文半径
    int[] p = new int[t.length()];
    // mx 是现有的所有回文子串中，最大的右边界（回文子串不包括 mx）
    int mx = 0;
    // id 是上述 mx 对应回文子串的中心点
    int id = 0;
    // 最长回文子串的长度及其中心位置索引
    int maxLen = -1;
    int maxIndex = -1;
    // 遍历字符串（不用包括两边加上的 $ 和 @）
    for (int i = 1; i < t.length() - 1; i++) {
        // 利用前面的信息更新 p[i]
        p[i] = mx > i? Math.min(p[2 * id - i], mx - i) : 1;
        // 向两边延伸，让 p[i] 达到最大
        while (t.charAt(i + p[i]) == t.charAt(i - p[i])) {
            p[i]++;
        }
        // 更新 id 和 mx
        if (p[i] + i > mx) {
            mx = p[i] + i;
            id = i;
        }
        // 更新 maxLen 和 maxIndex
        if (p[i] - 1 > maxLen) {
            maxLen = p[i] - 1;
            maxIndex = i;
        }
    }

    // 第三步：计算回文字符串的起始索引
    int start = (maxIndex - maxLen) / 2;

    return s.substring(start, start + maxLen);
}

马拉车（Manacher）算法

简介