Manacher algorithm

2019/11/04 ALGO

Manacher’s Algorithm helps us find the longest palindromic substring in the given string. It optimizes over the brute force solution by using some insights into how palindromes work.

最长回文子串问题

给定一个字符串S,找到S中最长的回文子串。例如上图中,S=“abacabacabb”,其最长回文子串是“bacabacab”。

思路

解决的方法有很多,例如暴力法、动态规划、最长公共子串、中心拓展法,以及Manacher算法。我们先来看一看前四种解决思路。

暴力

暴力算法通过选出所有子字符串判断是否回文,然后选择最长的回文子串。假设输入字符串的长度是n,那么总共有

个子字符串。验证每个子字符串是否为回文串需要的时间,总的时间复杂度是。由于不需要额外的空间,所以空间复杂度是

动态规划

以“ababa”为例,如果我们知道了“bab”是回文串,那么显然“ababa”也是回文串,因为它在原来子串的基础上左右加上了相同的元素。我们定义

因此有动态规划方程式

创建一个二维数组dp,其中dp[i][j]=1表示是回文子串,否则为0。这个二维数组的初始状态为

  • dp[i][i] = 1,单个字符是回文串
  • dp[i][i+1] = 1 if S[i] == S[i+1],连续两个相同字符是回文串

最长公共子串

将输入的字符串S翻转得到Rev,求字符串S与Rev的最长公共子串,然后判断下标是否匹配就能求出结果。为什么需要额外的下标匹配呢?例如S=“abc435cba”,它的翻转字符串rev=“abc534cba”,有公共子串“abc”、“cba”,但是这两个答案都不是回文串。原因是对应的子串翻转后他们的下标没有逐个匹配,在S中,子字符串“cba”的下标区间是[6,8],那么对应的翻转之后匹配的下标区间是[0,2],所以要除了要找出最长公共子串之外,还要求下标区间是相匹配的。

例如S=“abacabacabbef”,对应的翻转字符串rev=“febbacabacaba”,它们的最长公共子字符串是“bacabacab”,前者的下标区间是[1,9],后者的下标区间是[3,11],满足1+11=12,3+9=12,因此下标区间是相匹配的。所以结果就是其最长公共子串“bacabacab”。

该方法与动态规划的方法类似,使用了的空间来储存表,时间运行复杂度是

中心拓展法

回文串的中心两侧互为镜像,所以回文串可以从它的中心开始展开,不断的判断左右两侧是否满足镜像。这样的中心总共有n+n-1 = 2n-1个。

围绕中心开展的扩展回文需要消耗时间,总共有2n-1次循环,时间复杂度为,而在空间上的复杂度为

Manacher算法

Manacher在1975年发表一篇论文,提出了在线性时间内解决最长回文子串问题的算法。我们又把它称为“马拉车算法”。这个方法最大的贡献是将时间复杂度提高到线性时间。

下面不予以证明该算法,给出该算法的演算过程。以S=“abacabacabb”为例。

我们定义几个符号。上图中,字母i表示字符串S的下标,字母l表示已经找到的最长回文串的左边界,字母r表示已经找到的最长回文串的右边界,字母c表示已经找到的最长回文串的中心。看起来有点绕口,总的来说,l、c、r是已经找到的最长回文串的属性。算法的任务是计算出每个下标i作为中心的最长的回文串。

上图中,下标j与下标j’以中心c相互成对称,我们称下标j’是下标j的影子下标。

算法的思路与中心拓展法相似,使用一个数组P来保存每个下标i所能找到的最长的拓展长度。例如上图中P[4]=3,是因为以S[3]=’C’为中心的最长回文子串的拓展长度是3,所以直到遍历下标3为止,能找到的最长回文子串的长度为3+3+1=7,也就是“abacaba”。

马拉车算法与中心拓展法不同的地方在于在计算拓展长度的时候不是重新遍历,而是先选取影子下标的值。例如上图中P[4]应该如何计算?按照中心拓展法的思路,从S[4]的左边右边开始遍历,判断是否相等,然后增加拓展长度。而马拉车算法无需重新遍历,而是直接选择影子坐标P[2]的值。这个思路是显而易见的,首先P[4]对应的字符S[4]处于边界[l,r]中,也就是说它的影子坐标一定存在。而先前的影子坐标已经遍历过左右的中心拓展了,那么对于P[4]而言它的拓展结果是一致的(因为对称性),所以它可以在影子坐标的值的基础上继续拓展,更新边界l、r以及中心点c。

这里会存在一个问题,那就是当回文子串是偶数怎么办?这样就找不到中心点c了。我们可以对字符串进行预处理,使其变为奇数。以下图为例,预处理之后的结果是“^#c#b#c#b#c#c#d#e#$”。经过拓展之后,原本P数组的含义是以该字符为中心的最长拓展距离,现在也可以理解为以该字符为中心的最长回文子串长度。例如上图中,P[6]=5,这个5可以表示为以字符c为中心的最长拓展距离,也可以理解为以字符c为中心的最长回文子串长度(cbcbc)。因此经过处理之后,只需要找到P数组的最大值。

马拉车算法的时间复杂度是,空间复杂度是。下面是参考代码:

class Solution {
public:
    string longestPalindrome(string s) {
        // 对字符串s进行预处理
        string ans;
        for(int i=0; i<s.size(); i++){
            ans += s[i];
            ans += '#';
        }
        if(s.size() != 0){
            ans.erase(ans.size()-1);
            ans = "^#" + ans + "#$";
        } else {
            ans = "^$";
        }

        int n = ans.size();
        // 拓展长度数组P、中心点C、右边界R
        // 左边界L可以通过C和R计算得出,这里不需要
        vector<int> P(n, 0);
        int C = 0, R = 0;

        for(int i=1; i<n-1; i++){
            // 下标i的影子下标i_mirror
            int i_mirror = 2 * C - i;
            if(R > i)
                P[i] = min(R-i, P[i_mirror]);
            else
                P[i] = 0;
            
            // 中心拓展法
            // 更新中心点C和右边界R
            while(ans[i+1+P[i]] == ans[i-1-P[i]])
                P[i]++;
            if(i + P[i] > R){
                C = i;
                R = i+P[i];
            }
        }

        // 寻找P数组的最大值
        int _t = 0;
        int _i = 0;
        for(int i=1; i<n-1; i++){
            if(P[i] > _t){
                _t = P[i];
                _i = i;
            }
        }
        int _s = (_i - _t)/2;
        return s.substr(_s, _t);
    }
};

参考资料

  • Manacher, Glenn (1975), “A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string”, Journal of the ACM, 22 (3): 346–351, doi:10.1145/321892.321896.
  • https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode/
  • https://medium.com/hackernoon/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96f

Search

    Table of Contents