老司机开车，教会女朋友什么是「马拉车算法」

马拉车算法是用来 查找一个字符串的最长回文子串的线性方法 &＃xff0c;由一个叫 Manacher 的人在 1975 年发明的&＃xff0c;这个方法的牛逼之处在于将时间复杂度提升到了 线性 。

事实上&＃xff0c;马拉车算法在思想上和 KMP 字符串匹配算法有相似之处&＃xff0c;都避免做了很多重复的工作。

如果你觉得马拉车算法的中文称呼有点俗&＃xff0c;那么 KMP算法 就是带了一点颜色了&＃xff0c;你总能在有关于 KMP算法 介绍的文章留言区看到它的中文俗称。

Manacher 算法本质上还是 中心扩散法 &＃xff0c;只不过它使用了类似 KMP 算法的技巧&＃xff0c;充分挖掘了已经进行回文判定的子串的特点&＃xff0c;提高算法的效率。

下面介绍 Manacher 算法的运行流程。

首先还是“中心扩散法”的思想&＃xff1a;回文串可分为奇数回文串和偶数回文串&＃xff0c;它们的区别是&＃xff1a;奇数回文串关于它的“中点”满足“中心对称”&＃xff0c;偶数回文串关于它“中间的两个点”满足“中心对称”。

为了避免对于回文串字符个数为奇数还是偶数的套路&＃xff0c;首先对原始字符串进行预处理&＃xff0c;方法也很简单&＃xff1a;添加分隔符。

第一步是对原始字符串进行预处理&＃xff0c;也就是 添加分隔符 。

首先在字符串的首尾、相邻的字符中插入分隔符&＃xff0c;例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。

对这一点有如下说明&＃xff1a;

1、分隔符是一个字符&＃xff0c;种类也只有一个&＃xff0c;并且这个字符一定不能是原始字符串中出现过的字符&＃xff1b;

2、加入了分隔符以后&＃xff0c;使得“间隙”有了具体的位置&＃xff0c;方便后续的讨论&＃xff0c;并且新字符串中的任意一个回文子串在原始字符串中的一定能找到唯一的一个回文子串与之对应&＃xff0c;因此对新字符串的回文子串的研究就能得到原始字符串的回文子串&＃xff1b;

3、新字符串的回文子串的长度一定是奇数&＃xff1b;

4、新字符串的回文子串一定以分隔符作为两边的边界&＃xff0c;因此分隔符起到“哨兵”的作用。

辅助数组 p 记录了新字符串中以每个字符为中心的回文子串的信息。

手动的计算方法仍然是“中心扩散法”&＃xff0c;此时记录以当前字符为中心&＃xff0c;向左右两边同时扩散&＃xff0c;记录能够扩散的最大步数。

以字符串 "abbabb" 为例&＃xff0c;说明如何手动计算得到辅助数组 p &＃xff0c;我们要填的就是下面这张表。

第 1 行数组 char &＃xff1a;原始字符串加上分隔符以后的每个字符。

第 2 行数组 index &＃xff1a;这个数组是新字符串的索引数组&＃xff0c;它的值是从 $0$ 开始的索引编号。

以 char[0] &＃61; &＃39;#&＃39; 为中心&＃xff0c;同时向左边向右扩散&＃xff0c;走 $1$ 步就碰到边界了&＃xff0c;因此能扩散的步数为 $0$&＃xff0c;因此 p[0] &＃61; 0&＃xff1b;

以 char[1] &＃61; &＃39;a&＃39; 为中心&＃xff0c;同时向左边向右扩散&＃xff0c;走 $1$ 步&＃xff0c;左右都是 "#"&＃xff0c;构成回文子串&＃xff0c;于是再继续同时向左边向右边扩散&＃xff0c;左边就碰到边界了&＃xff0c;最多能扩散的步数”为 $1$&＃xff0c;因此 p[1] &＃61; 1&＃xff1b;

以 char[2] &＃61; &＃39;#&＃39; 为中心&＃xff0c;同时向左边向右扩散&＃xff0c;走 $1$ 步&＃xff0c;左边是 "a"&＃xff0c;右边是 "b"&＃xff0c;不匹配&＃xff0c;最多能扩散的步数为 $0$&＃xff0c;因此 p[2] &＃61; 0&＃xff1b;

以 char[3] &＃61; &＃39;b&＃39; 为中心&＃xff0c;同时向左边向右扩散&＃xff0c;走 $1$ 步&＃xff0c;左右两边都是 “#”&＃xff0c;构成回文子串&＃xff0c;继续同时向左边向右扩散&＃xff0c;左边是 "a"&＃xff0c;右边是 "b"&＃xff0c;不匹配&＃xff0c;最多能扩散的步数为 $1$ &＃xff0c;因此 p[3] &＃61; 1&＃xff1b;

以 char[4] &＃61; &＃39;#&＃39; 为中心&＃xff0c;同时向左边向右扩散&＃xff0c;最多可以走 $4$ 步&＃xff0c;左边到达左边界&＃xff0c;因此 p[4] &＃61; 4。

分析到这里&＃xff0c;后面的数字不难填出&＃xff0c;最后写成如下表格&＃xff1a;

说明&＃xff1a;有些资料将辅助数组 p 定义为回文半径数组&＃xff0c;即 p[i] 记录了以新字符串第 i 个字符为中心的回文字符串的半径&＃xff08;包括第 i 个字符&＃xff09;&＃xff0c;与我们这里定义的辅助数组 p 有一个字符的偏差&＃xff0c;本质上是一样的。

下面是辅助数组 p 的结论&＃xff1a;辅助数组 p 的最大值是 $5$&＃xff0c;对应了原字符串 "abbabb" 的  “最长回文子串” &＃xff1a;"bbabb"。这个结论具有一般性&＃xff0c;即&＃xff1a;

辅助数组 &＃96;p&＃96; 的最大值就是“最长回文子串”的长度

因此&＃xff0c;我们可以在计算辅助数组 p 的过程中记录这个最大值&＃xff0c;并且记录最长回文子串。

简单说明一下这是为什么&＃xff1a;

如果新回文子串的中心是一个字符&＃xff0c;那么原始回文子串的中心也是一个字符&＃xff0c;在新回文子串中&＃xff0c;向两边扩散的特点是&＃xff1a;“先分隔符&＃xff0c;后字符”&＃xff0c;同样扩散的步数因为有分隔符 # 的作用&＃xff0c;在新字符串中每扩散两步&＃xff0c;虽然实际上只扫到一个有效字符&＃xff0c;但是相当于在原始字符串中相当于计算了两个字符。

因为最后一定以分隔符结尾&＃xff0c;还要计算一个&＃xff0c;正好这个就可以把原始回文子串的中心算进去&＃xff1b;

如果新回文子串的中心是 #&＃xff0c;那么原始回文子串的中心就是一个“空隙”。在新回文子串中&＃xff0c;向两边扩散的特点是&＃xff1a;“先字符&＃xff0c;后分隔符”&＃xff0c;扩散的步数因为有分隔符  # 的作用&＃xff0c;在新字符串中每扩散两步&＃xff0c;虽然实际上只扫到一个有效字符&＃xff0c;但是相当于在原始字符串中相当于计算了两个字符。

因此&＃xff0c;“辅助数组 p 的最大值就是“最长回文子串”的长度”这个结论是成立的&＃xff0c;可以看下面的图理解上面说的 $2$ 点。

写到这里&＃xff0c;其实已经能写出一版代码。&＃xff08;注&＃xff1a;本文的代码是结合了 LeetCode 第 5 题「最长回文子串」进行讲解&＃xff09;

public class Solution {

    public String longestPalindrome(String s) {
        int len &＃61; s.length();
        if (len < 2) {
            return s;
        }
        String str &＃61; addBoundaries(s, &＃39;#&＃39;);
        int sLen &＃61; 2 * len &＃43; 1;
        int maxLen &＃61; 1;

        int start &＃61; 0;
        for (int i &＃61; 0; i < sLen; i&＃43;&＃43;) {
            int curLen &＃61; centerSpread(str, i);
            if (curLen > maxLen) {
                maxLen &＃61; curLen;
                start &＃61; (i - maxLen) / 2;
            }
        }
        return s.substring(start, start &＃43; maxLen);
    }

    private int centerSpread(String s, int center) {
        // left &＃61; right 的时候&＃xff0c;此时回文中心是一个空隙&＃xff0c;回文串的长度是奇数
        // right &＃61; left &＃43; 1 的时候&＃xff0c;此时回文中心是任意一个字符&＃xff0c;回文串的长度是偶数
        int len &＃61; s.length();
        int i &＃61; center - 1;
        int j &＃61; center &＃43; 1;
        int step &＃61; 0;
        while (i >&＃61; 0 && j < len && s.charAt(i) &＃61;&＃61; s.charAt(j)) {
            i--;
            j&＃43;&＃43;;
            step&＃43;&＃43;;
        }
        return step;
    }


    /**
     * 创建预处理字符串
     *
     * &＃64;param s      原始字符串
     * &＃64;param divide 分隔字符
     * &＃64;return 使用分隔字符处理以后得到的字符串
     */
    private String addBoundaries(String s, char divide) {
        int len &＃61; s.length();
        if (len &＃61;&＃61; 0) {
            return "";
        }
        if (s.indexOf(divide) !&＃61; -1) {
            throw new IllegalArgumentException("参数错误&＃xff0c;您传递的分割字符&＃xff0c;在输入字符串中存在&＃xff01;");
        }
        StringBuilder stringBuilder &＃61; new StringBuilder();
        for (int i &＃61; 0; i < len; i&＃43;&＃43;) {
            stringBuilder.append(divide);
            stringBuilder.append(s.charAt(i));
        }
        stringBuilder.append(divide);
        return stringBuilder.toString();
    }
}

此时&＃xff0c;计算机科学家 Manacher 出现了&＃xff0c;他充分利用新字符串的回文性质&＃xff0c;计算辅助数组 p。

上面的代码不太智能的地方是&＃xff0c;对新字符串每一个位置进行中心扩散&＃xff0c;会导致原始字符串的每一个字符被访问多次&＃xff0c;一个比较极端的情况就是&＃xff1a;#a#a#a#a#a#a#a#a#。

事实上&＃xff0c;计算机科学家 Manacher 就改进了这种算法&＃xff0c;使得在填写新的辅助数组 p 的值的时候&＃xff0c;能够参考已经填写过的辅助数组 p 的值&＃xff0c;使得新字符串每个字符只访问了一次&＃xff0c;整体时间复杂度由 O(N²) 改进到 $O(N)$。

具体做法是&＃xff1a;在遍历的过程中&＃xff0c;除了循环变量 i 以外&＃xff0c;我们还需要记录两个变量&＃xff0c;它们是 maxRight 和 center &＃xff0c;它们分别的含义如下&＃xff1a;

maxRight 表示记录当前向右扩展的最远边界&＃xff0c;即从开始到现在使用“中心扩散法”能得到的回文子串&＃xff0c;它能延伸到的最右端的位置 。

对于 maxRight 我们说明 3 点&＃xff1a;

center 是与 maxRight 相关的一个变量&＃xff0c;它是上述 maxRight 的回文中心的索引值。对于 center 的说明如下&＃xff1a;

center 的形式化定义&＃xff1a;

说明&＃xff1a;x &＃43; p[x] 的最大值就是我们定义的 maxRight&＃xff0c;i 是循环变量&＃xff0c;0<&＃61; x 表示是在 i 之前的所有索引里得到的最大值  maxRight&＃xff0c;它对应的回文中心索引就是上述式子。