leetcode 5. 最长回文子串 (Manacher's Algorithm)

leetcode 5. 最长回文子串 (Manacher's Algorithm)
传统方法:遍历每一个字符,以该字符为中点向两边查找。
问题1: 由于回文串长度的奇偶性,需要对对称轴的位置进行分别判断,这种解法的时间复杂度是O(n^2)。
如aabb对称轴为ab之间,而ababa对称轴为中间的a 需要分别对两种情况进行判断
问题2:子串被重复多次访问,降低了时间效率。

Manacher's Algorithm

Manacher's Algorithm,中文名叫马拉车算法,是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串,神奇之处在于将算法的时间复杂度精进到了O(n),下面我们来详细介绍下这个算法的思路。

预处理

回文字符串以其长度来分,可以分为奇回文(如abcba)、偶回文(如aabb),一般情况下需要分两种情况来寻找回文,马拉车算法为了简化这一步,对原始字符串进行了处理,在每一个字符的左右两边都加上特殊字符(肯定不存在于原字符串中的字符 如"#"),让字符串变成一个奇回文。

'ababa'---> '#a#b#a#b#a#'
'abccba'---> '#a#b#c#c#b#a#'

Manacher算法核心

回文半径:回文串最左或最右字符到其对称轴的距离
MaxRight:当前所有回文串所能触及到的最右字符的位置
pos:Maxright对应的回文串的回文中心的位置
maxpos:当前最长回文串的回文中心
maxr:当前最长回文串的回文半径
p[]:存储以i位置为回文中心的回文半径值


我们从左往右地访问字符串来求p[i],pos是遍历到的所有回文子串中MaxRight最大时会问中心的位置,所以必然有pos<=i。对于i的位置(在Maxright左边或右边)分情况讨论:

1.当i<MaxRight时:
如下图所示,MaxRight'为MaxRight关于pos对称的位置。
i关于pos的对称位置j,这个j对应的p[j]在之前的遍历已经算过了
根据回文串的对称性,以i为对称轴的回文串和以j为对称轴的回文串,有一部分是相同的。这里又有两种细分的情况:
情况1:j的回文区域在MaxRight对应回文串的内部,此时i的回文半径与 j 相同,我们可以直接得到i的回文半径 p[i]=p[j]=p[2*pos-i]
leetcode 5. 最长回文子串 (Manacher's Algorithm)

情况2:j的回文区域在MaxRight对应回文串的外部
这时我们只能确定MaxRight-i 的部分是以i为对称轴的回文半径
leetcode 5. 最长回文子串 (Manacher's Algorithm)

所以综合以上两种情况 p[i]=min(p[2*pos-i],max-i);

2.当i>MaxRight时:
说明以i为对称轴的回文串还没有任何一个部分被访问过,于是只能从i的左右两边开始尝试扩展了,因此直接使p[i]=1;
代码:

class Solution {
public:
    string longestPalindrome(string s) {
        if(!s.length()) return "";
        string str;
        for(int i=0;i<s.length();i++){
            str+='#';
            str+=s[i];
        }//预处理
        str+='#';
        int len=str.length();
        int maxright=0,maxpos=0,maxr=0,pos=0;
        int*p=new int[len];
        memset(p,0,len*sizeof(int));
        for(int i=0;i<len;i++){
            if(i<maxright){
                p[i]=min(p[2*pos-i],maxright-i);
            }
            else{
                p[i]=1;
            }
            while((i-p[i]>=0)&&(i+p[i]<len)&&(str[i-p[i]]==str[i+p[i]])){
				//i-p[i]>=0保证回文串最左元素位置>=0
				//i+p[i]<len 保证回文串长度不超过总长度
				//str[i-p[i]]==str[i+p[i]] 向两边扩展的条件
				p[i]++;
            }
            if(i+p[i]>maxright){
                maxright=i+p[i];
                pos=i;
            }
            if(p[i]>maxr){
                maxr=p[i];
                maxpos=i;
            }
        }
        return s.substr((maxpos-maxr+1)/2,maxr-1);
    }
};
上一篇:ALGORITHM:Sort-MergeSort


下一篇:Advanced Algorithm Lecture1(高等算法笔记)