c

cnspary

V1

2022/02/04阅读:44主题:默认主题

最长回文子串算法详解

# Given a string s, return the longest palindromic substring in s.

class Solution:        
    def longestPalindrome(self, s: str) -> str:

首先解释下什么叫做回文:正读和反读都相同的字符序列为回文( Palindrome )。比如:abcba。但注意 daab 不是回文,因为 d 与 b 是镜像关系。

在这里我会介绍这道题目的最优算法:Manacher (马拉车)算法,时间复杂度为


在介绍 Manacher 算法之前,我们先来看看关于这道题的一个非常直观的算法:中心拓展法:以每个字符为中心,分别向左和向右拓展,求得回文子串,最后在所有的回文子串中取最长者。

class Solution:        
    def longestPalindrome(self, s: str) -> str:
        paliString = ""
        maxLength = -1
      
        for i in range(len(s)):
            l = i - 1
            r = i + 1
        
            while -1 < l and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1

            if r - l - 1 > maxLength:
                maxLength = r - l - 1
                paliString = s[l+1: r]
          
        return paliString

很可惜,以上这个算法并没有包含所有的情况,因为一个回文串的中心不一定是字符,比如:abba。所以以上这个算法只适用于⻓度为奇数的情况。当然我们稍加修改把偶数的情况考虑进去,这里就不实现了。

考虑下以上这个算法的时间复杂度:很明显对于每个字符位置在最坏情况下我们都要向右或向左尽可能的拓展,因此总体的时间复杂度量级应该为

中心拓展算法之所以效率不高,是因为其没有很好的利用回文的特性:对称性,接下来我将介绍 Manacher 算法,通过利用对称性,将算法的时间复杂度降至


Manacher 算法

如何规避奇偶长度问题?

在上面介绍的中心拓展算法中,我们遇到一个回文长度奇偶的问题,为了处理这个问题,首先我们要对字符串进行改造

为什么要这么处理呢?因为此时无论回文串⻓度是奇数还是偶数,我们处理的逻辑是严格相同的(因为都转化成了长度为奇数的情况),例如:

s = aba -> s‘ = #a#b#a# 回文的中心是 b

s = abba -> s’ = #a#b#b#a# 回文的中心是 #,也就是原本 s 中 b 与 b 之间的平分线

同时利用程序语言中的整数除法的性质,又可以很轻易的从 s' 定位 s 中的位置。

如何利用对称性?

Manacher 算法之所高效,就是因为它利用了回文的对称性,来看下面这个例子:

我们已知在 之间是一个回文子串,中心为 center。当前的指针指向 current,我们需要求得以 current 为中心的回文串。根据对称性,在 center 的左边 mirror 处必然存在一个相同的字符。又由于算法是从左向右进行的,mirror 处的回文串的⻓度已经计算出来,那么 current 处的回文串的⻓度可能mirror 处的回文串的⻓度一致 (不一定严格一致)。利用这点我们可以减少大量的重复性判断。

需要解释下为什么上面说的是可能一致,这个地方是很容易忽视的,我们通过以下两个例子来解释:

如上图,mirror 处的回文串,严格落在 ,那么此时很明显 current 处的回文串和 mirror 处的是严格一致的。

另一种情况,mirror 处的回文串边界抵达了最左侧边界 L,根据对称性,current 的回文串的边界也必然抵达了最右侧边界 R,但当前我们已知的范围为 ,因此在 R 处是否存在一个字符使得 current 的回文串长度增加,我们无法直接得到,需要使用拓展法来求得。

总结下:第一种情况下,我们可以确切的知道 current 处的回文串长度,第二种情况,虽然我们不知道确切的长度,但至少我们可以知道 current 处的回文串的右边界至少是 R,那么其回文串的⻓度至少是 ,由此我们得到以下关系:

如何记录对称性信息?

我们已经知道通过对称性我们可以更高效的求解,那么我们如何记录对称性信息呢?我们给出信息表 P-array 如下:

P[i] 为以 s'[i] 为 center,向左右两侧拓展可以得到的最长回文子串的半径。

同时我们还需要记录 current 所在的回文串的最大右边界以及 center 信息。

实现

def longestPalindrome(self, s: str) -> str: 
    1. 对 s 进行改造 得到 s'
    2. 初始化 P 数组
    3. 由左至右遍历 s'
        3.1 current 落在某个 center 的 回文子串的范围内部: 由上面说的对称性,计算 current 处的最⻓回文子串;
        3.2 current 落在 R 或者 其回文范围可能超过 R: 使用中心拓展法,求得 current 处的最⻓回文子串 同时更新最右的边界;
        3.3 若cur处的回文子串更⻓,则更新; 
    返回结果

算法整个流程是从左向右扫描,如果 current 处在之前的某个以 center 为中心,R 为右边界的回文串内部,我们先利用对称性判断。如果 current 回文串范围超过之前所求的的最大右边界,就利用中心拓展处理,更新最大右边界和 center

具体实现如下:

class Solution:        
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s

        def expend(s: str) -> str:
            # 这里拓展将 aba -> (#a#b#a#)
            # leetcode的测试数据应该都是 a~z的 所以添加了左右括号
            # 保证了最左最右的字符不同,不至于下溢 上溢
            news = "(#"
            for c in s:
                news += c
                news += '#'
            news += ')'
            return news

        news = expend(s)

        P = [1 for _ in range(len(news))]

        maxRatio = -1
        maxCenter = -1

        maxR = 0
        center = 0

        for c in range(1, len(news) - 1):
            if c < maxR:
                P[c] = min(P[2 * center - c], maxR - c)

            while news[c - P[c]] == news[c + P[c]]:
                P[c] += 1

            if c + P[c] > maxR:
                center = c
                maxR = c + P[c]

            if P[c] - 1 > maxRatio:
                maxRatio = P[c] - 1
                maxCenter = c

        a = (maxCenter - maxRatio) // 2
        return s[a: a+maxRatio]

最后我们来分析下 Manacher 算法的时间复杂度,很显然对于每个点要么我们可以通过之前的回文串直接得出答案,要么向左向右进行拓展判断。在进行拓展判断的时候,maxR 至少增加 1,每次循环中 current 也至少增加 1, 因此对于每一轮循环,current + maxR 至少增加 1, 而 current + maxR 最多不超过 , 因此整体算法的时间复杂度为

分类:

其他

标签:

其他

作者介绍

c
cnspary
V1