CodingTour —

Manacher

从字符串 babadada 中找出最长回文子串：adada。

暴力破解的方式略过。一种优化后的方法是：

1. 在循环遍历的过程中从中心往两边拓展来找回文子串
2. 用一个集合记录每个索引的回文长度

具体过程如下：

i = 1
lengths = [0, 0, 0, 0, 0, 0, 0, 0]

babadada
 ^
 i

lengths[i] = 1
-----------------------------------------------------------------------------
i = 2
lengths = [0, 1, 0, 0, 0, 0, 0, 0]

babadada
  ^
  i

lengths[i] = 1
-----------------------------------------------------------------------------
i = 3
lengths = [0, 1, 1, 0, 0, 0, 0, 0]

babadada
   ^
   i

lengths[i] = 0
-----------------------------------------------------------------------------
i = 4
lengths = [0, 1, 1, 0, 0, 0, 0, 0]

babadada
    ^
    i

lengths[i] = 1
-----------------------------------------------------------------------------
i = 5
lengths = [0, 1, 1, 0, 1, 0, 0, 0]

babadada
     ^
     i

lengths[i] = 2
-----------------------------------------------------------------------------
i = 6
lengths = [0, 1, 1, 0, 1, 2, 0, 0]

babadada
      ^
      i

lengths[i] = 1
-----------------------------------------------------------------------------
i = 7
lengths = [0, 1, 1, 0, 1, 2, 1, 0]

babadada
       ^
       i

lengths[i] = 0
-----------------------------------------------------------------------------
lengths = [0, 1, 1, 0, 1, 2, 1, 0]
babadada
   adada -> 最长回文子串，中心索引为5，长度为5(左右两边各有2)
     ^
     5

这样一来，因为需要内外两层循环，时间复杂度就控制在 \(O({n^2})\) 了。

但是内层循环是必须的吗？观察后可以发现，以索引 4、5、6 为例：

babadada
    ^^^
    456
    
lengths = [
    ...
    1, 2, 1
    ...
]

已知索引 4 的回文长度为1，索引 5 的回文长度为2，那么在忽略边界的情况下，因为 5 包含了 4，而回文又是对称的，所以可以直接得出索引 6 的长度也为1。

Manacher 算法就是利用了这一点，通过记录已遍历到的最大右边界来避免不必要的内循环，事实上它做到了 \(O(n)\) 的时间复杂度。规则如下：

• 先用 # 将每一个字符包裹起来，这样就不用担心回文是奇数还是偶数
• 记录遍历到的最大右边界和到达这个边界的回文中心点，处理好以下几种情况：
  • 如果当前索引大于等于右边界，则老老实实一个一个去匹配，匹配完后记录右边界和当前索引
  • 如果当前索引小于右边界，则通过和右边界中心点计算，得到对称索引下的回文长度值，基于这个长度，如果：
    • 长度值加上当前索引超过了右边界时，要主动将长度截断到右边界，之后从超出的部分老老实实一个一个匹配，匹配完后记录右边界和当前索引
    • 长度值加上当前索引没有超过了右边界时，直接使用该长度值，继续遍历下一个数

大致规则就是这样，这里有一个简洁的实现：

class Solution:
    #Manacher algorithm
    #https://en.wikipedia.org/wiki/Longest_palindromic_substring
    
    def longestPalindrome(self, s):
        # Transform S into T.
        # For example, S = "abba", T = "^#a#b#b#a#$".
        # ^ and $ signs are sentinels appended to each end to avoid bounds checking
        T = '#'.join('^{}$'.format(s))
        n = len(T)
        P = [0] * n
        C = R = 0
        for i in range (1, n-1):
            P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
            # Attempt to expand palindrome centered at i
            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1
    
            # If palindrome centered at i expand past R,
            # adjust center based on expanded palindrome.
            if i + P[i] > R:
                C, R = i, i + P[i]
    
        # Find the maximum element in P.
        maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
        return s[(centerIndex  - maxLen)//2: (centerIndex  + maxLen)//2]

这个实现充满了 trick，比如:

1. '#'.join('^{}$'.format(s))，在字符串前后加上 ^ 、$，这样当遇到边界的时候直接中断了，不用使用像 index - nums[index] - 1 >= 0 and index + nums[index] + 1 < filled_length 这样的判断条件
2. (R > i) and min(R - i, P[2*C - i])，这条语句处理了以下情况：
   1. 如果当前索引大于等于右边界
   2. 如果当前索引小于右边:
      1. 长度值加上当前索引超过了右边界时
      2. 长度值加上当前索引没有超过了右边界时

更加详细的理论分析参见：Manacher’s Algorithm – Linear Time Longest Palindromic Substring