Manacher's Algorithm 马拉车算法

题目：Longest Palindromic Substring

题目简述

找出最长回文子串，如输入"babad"，结果为"bab"或"aba"。

马拉车算法

引入

可以观察到回文串根据中心对称，反之可以从中心向两边扩张去寻找最大回文串。一共有2n+1个中心，每个都尝试一下便可以得出答案。为了操作方便，添加分隔符#。
如：babaabac——> #b#a#b#a#a#b#a#c

image.png

T为加分割符后的字符串，L[i]代表以T[i]为中心的最长回文子串的长度。最后找出最大的L为13，（13-1）/2后为原字符串的最长回文子串的长度。

上述算法时间复杂度为O(n2）,在具体求解每个L[i]时都需要O(n)的时间复杂度，有没有办法可以提高效率呢？

若从左向右遍历求解，回文串的特性可以发挥一定作用。设L[0]-L[8]已求出，且已经得知T[8]为中心,左边界为T[2],右边界为T[14]是回文串。那么接下来L[9]=L[7]=3,L[10]=L[6]=1,.....，但注意L[3]!=L[13]。具体分析看下文。

根据回文特性简化

若前面已经求出了以C为中心，R为右边界的某个回文串，现在正要求的以i为中心的最大回文串长度。若i<=R，则可以根据对称规则求解，若i>R则只能蛮力求解。

设P为回文半径，即表示以字符T[i]为中心的最长回文字串的最端右字符到T[i]的长度。注：P[i]-1 即为原回文子串的长度

四种情况

1. i>R
   T[i-1]与T[i+1]匹配...T[i-2]与T[i+2]匹配...直至超出字符串边界，或T[i-k]!=T[i+k]

2. i<=R且i+(P[i']-1)<R
   P[i] = P[i']

3. i<=R且i+(P[i']-1)>R
   P[i] = R-i+1
   例:如下图，由于T[15]!=T[11]回文串被截断

   
   截断.jpg
   

   有没有可能T[15]==T[11]呢？
   若T[15]=T[11]（已知T[11]=T[5]=T[1]），则T[1]=T[15]，P[8]=7+1与P[8]=7矛盾，所以T[15]不可能等于T[11]。因此一定会被截断。

4. i<=R且i+(P[i']-1)=R
   P[i]>=R-i+1
   首先，P[i]至少可以是R-i+1，后面可能会有其他的字符使得回文子串继续加长，但也可能没有。具体有没有需要再一一匹配，但匹配的基础是R-i+1。T[i-(R-i+1)]与T[(i+(R-i+1)]匹配..T[i-(R-i+2)]与T[(i+(R-i+2)]匹配...

Python代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        c = 0
        r = -1
        T = '#' + '#'.join(s) + '#'
        P = [1]*(len(T))
        max_index = 0
        for i in range(len(T)):
            if i<= r:
                P[i] = min(r-i+1,P[2*c-i])
            # Try to extend
            while i-P[i]>=0 and i+P[i]<len(T) and T[i+P[i]]==T[i-P[i]]:
                P[i] += 1
            # 循环中顺便找出最长回文子串的中心
            if P[i]>P[max_index]: 
                max_index = i
            if i+P[i]-1 >r:
                c = i
                r = i+P[i]-1
        #根据映射关系返回原子串
        return(s[(max_index-P[max_index]+2)//2:(max_index+P[max_index]-2)//2+1])
if __name__ == "__main__":
    l = 'babad'
    t = Solution()
    r = t.longestPalindrome(l)
    print(r)

总结

1. 通过加分割符的方法，使每个中心位置都可以取到，也使字符串长度统一为奇数
2. 马拉车算法主要运用的是回文串的特性

Reference:

1. https://www.hackerrank.com/topics/manachers-algorithm

2. http://javabin.cn/2018/manacher.html

3. https://www.cnblogs.com/love-yh/p/7072161.html