Manacher's Algorithm

马拉车算法

Posted by Hitigerzzz on May 25, 2018

Manacher’s Algorithm

前言

今天在刷 LeetCode 时做了一道求字符串回文个数的题,回文串就是正反读起来就是一样的,如“abba”。 我自己用了一种时间复杂度为 $O(N^2)$ 的解法,查看题解后学习了一种时间复杂度为 $O(N)$ 的解法——Manacher’s Algorithm,由一个叫 Manacher 的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,利用回文串的特性来避免重复计算的 ,这是非常了不起的。该算法也可用来求解最大回文串问题。

算法过程

  1. 预处理,改造字符串 s, 变为 t(transform 的意思),改造方法如下:

    在字符串 s 的字符之间和 s 的首尾都插入一个“#”,如:s=“abba”变为t=”#a#b#b#a#” 。我们会发现 s 的长度是4,而 t 的长度为9,长度变为奇数了。当 s =“abcba”,变化为 t=“#a#b#c#b#a#”,t 的长度为11,所以我们发现其改造的目的是将字符串的长度变为奇数,这样就可以统一的处理奇偶的情况了

  2. 用一个数组 radius ,radius[i] 对应以 t[i] 为中心的回文半径,表示以字符 t[i] 为中心的最长回文字串的最端右字符到 t[i] 的长度,如以 t[ i ] 为中心的最长回文子串的下标区间为 [L, R],那么radius[ i ] = R-i。

    这里要注意 :由于第一个和最后一个字符都是#号,且也需要搜索回文,为了防止越界,我们还需要在首尾再加上非#号字符 ,如 @,$。

    举个例子

    index 0 1 2 3 4 5 6 7 8
    t @ # a # b # a # $
    radius[] 0 0 1 0 3 0 1 0 0

    数组 radius 有个性质,(radius[i] + 1) / 2,为以 t[i] 为中心回文串的个数,如例子中 i = 4 时,t[i] = b,以 t[i] 为中心的回文串有 b, aba 两个,等于 (3 + 1)/ 2。 i = 2 时,t[i] = a,以 t[i] 为中心的回文串有 a 一个,等于 (1 + 1)/ 2。

    这样一来,我们求解题目就变成求 radius 数组中所有 (radius[i] + 1) / 2 的和。

  3. 如何求 radius[]

    这里是 Manacher’s Algorithm 的核心。

    分情况讨论:

    1. 当 i <= R 时,如何计算 radius[i] 的值?毫无疑问的是数组 radius 中点 i 之前点对应的值都已经计算出来了。利用回文串的特性,我们找到点 i 关于中心点 Mi 的对称点 j ,其值为 j= 2*Mi-i 。

      a) 如果 radius[j] < R-i (同样是L和j 之间的距离),说明以点 j 为中心的回文串没有超出范围[L ,R],由回文串的特性可知,从左右两端向Mi遍历,两端对应的字符都是相等的。所以radius[i]=radius[j],如下图:

      b) 如果 radius[ j ] >= R-i (即 j 为中心的回文串的最左端超过 L),如下图所示。即以点 j为中心的最大回文串的范围已经超出了范围[L ,R] ,这种情况,等式 radius[ j ] = radius[ i ] 不总是成立的。因以点 j 为中心的回文串的最左端超过L,那么在[ L, j ]之间的字符肯定能在( j, Mi ]找到相等的,由回文串的特性可知,radius[ i ] 至少等于 R- i,至于是否大于 R-i(图中红色的部分),我们还要从 R+1 开始一一的匹配,直达失配为止,从而更新 R 和对应的 Mi 以及 radius[ i ]。

    2. 当 i > R时,如下图。这种情况,无法利用之前计算得出的结果,只能老老实实的一步步去匹配。

实现代码

public int countSubstrings(String s) {
    char[] t = new char[2 * s.length() + 3];
    t[0] = '@';
    t[1] = '#';
    t[t.length - 1] = '$';
    int pos = 2;
    for (char c : s.toCharArray()) {
        t[pos++] = c;
        t[pos++] = '#';
    }
    int[] radius = new int[t.length];
    int center = 0, right = 0;
    for (int i = 1; i < radius.length - 1; i++) {
        if (i < right) {
            radius[i] = Math.min(right - i, radius[2 * center - i]);
        }
        while (t[i + radius[i] + 1] == t[i - radius[i] - 1]) {
            radius[i]++;
        }
        if (i + radius[i] > right) {
            center = i;
            right = i + radius[i];
        }
    }
    int ans = 0;
    for (int len : radius) {
        ans += (len + 1) / 2;
    }
    return ans;
}

代码易错点:

  1. 13 行循环的起始位置,这里要排除掉开头的 @ 和结尾的 $
  2. 27行 ans += (len + 1) / 2; 正确理解找到对应的公式

参考文章

Manacher’s Algorithm —-马拉车算法