最长回文子串（马拉车算法）

男娘i 2024-04-17 06:28 75阅读 0赞

最长回文子串，即正反读起来都一样，例如“ababa”。Manacher Algorithm算法利用了回文的重复特性，让时间复杂度降为了O(n)。  
马拉车算法详解：

1.  改造字符串，在中心扩展法中，要求区分字符串长度为奇数或偶数的情况，我们这里对字符串进行简单的改造，让字符串变成奇数便于处理。例：“ababad” ---->“a\#b\#a\#b\#a\#d”。为了在检测回文子串的时候避免判断越界，我们可以在开头和结束添加两个不同的字符---->"$a\#b\#a\#b\#a\#d^"（也不可不做这一步，如果不在开头和结束添加两个不同的字符的话，就需要在检测回文子串的时候检测开头和结尾）
2.  为了能够充分利用回文子串的重复性质，我们可以将字符串中每个字符的回文半径存如一个数组P中
3.  这样就将问题转换为了求数组P中的最大值所在的下标和值。但在实际操作中我们并不这样做，是动态的寻着数组P的最大值，即一边写入一边检测，而不是等数组P填充完毕后再去寻找数组P的最大值。因为字符串"a\#a"和"\#a\#“虽然第一个字符串的”\#“和第二个字符串的"a"的回文半径是相同的，但是，显而易见，在去掉”\#“后 一个是"aa”，一个是"a"。
4.  关于如何填充数组P  
    先设置两个变量，马拉车算法就是在动态的更新这两个变量。  
    center：是最大回文子串的中心位置  
    mx\_right：是最大回文子串所能覆盖的最右端的位置。  
    共分为两种情况：  
    当 i < mx\_right时：即i位于目前的最大回文子串max\_str中。那么我们根据回文的重复特性，取检查j = 2 \* center - i(j为i以center为中心的对称点)。如果P\[j\] < mx\_right - i 说明以j为中心的回文子串依然位于目前的最大回文子串max\_str，很具重复特性可以知道此时P\[i\] == p\[j\]。如果P\[j\] >= mx\_right - i,此时只能保证到i的回文子串到mx\_right这位置是依然满足的，这里别无他法，只能暴力取匹配mx\_right外面的，直到失配，然后在根据大小判断是否更新最大回文子串max\_str  
    当i >= mx\_right时：此时不能充分利用回文子串的重复特性，只能暴力匹配。

def longestPainromedon(s:str):
    
        if len(s) < 1:
            return s
        new_str = '$' + '#'.join(s) + '^'		#避免判断越界
        center = 1					#最长回文子串中心位置
        mx_right = 1				#最长回文子串最右面覆盖的位置
        max_str = new_str[1]			#最长回文子串
        p = [0]*len(new_str)			#回文子串半径表列
        for i in range(1, len(new_str)-1):
    
            j = 2*center - i
            if i < mx_right:
                if p[j] < mx_right - i:
                    p[i] = p[j]
                else:
                    k = mx_right+1
                    while new_str[k] == new_str[2*i - k]:
                        k += 1
                    k -= 1
                    p[i] =  k - i
                    cur_str = new_str[i - p[i]:i + p[i] + 1].replace('#', '')
                    if len(cur_str) > len(max_str):
                        max_str = cur_str
                        center, mx_right = i, k
            else:
                k = 0
                while new_str[i - k - 1] == new_str[i + k + 1]:
                    k += 1
                p[i] = k
                cur_str = new_str[i - p[i]:i+p[i] + 1].replace('#', '')
                if len(cur_str) > len(max_str):
                    max_str = cur_str
                    center, mx_right = i, k + i
    
        return max_str

代码如上，此代码时完全照算法来的，其他的博客的代码我想应该是有所优化，导致我一开始有点懵。