最长回文子串Longest palindromic substring的四种算法

题目描述:

给定字符串$S$,求其最长的回文子串。

Leetcode:https://leetcode.com/problems/longest-palindromic-substring/

下面给出四种算法思路,分别是朴素枚举、动态规划、中心拓展和Manacher算法。

其中,Manacher算法复杂度为$O(n)$

1. 朴素枚举

时间复杂度:$O(n^3)$

枚举$S$的所有子串,判断子串是否为回文字符串,取其中最长子串。

def palindrome1(s):
    n = len(s)
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            if j-i+1>ans and s[i:j]==s[j:i:-1]:
                ans = j-i+1
    return ans               

2. 动态规划

时间复杂度:$O(n^2)$

注意到枚举子串并判断时产生了大量的重复判断,用状态$dp[i][j]$记录子串$s[i:j]$是否为回文字符串。枚举子串时按照子串长度的顺序进行枚举,若$s[i+1:j-1]$是回文串并且$s[i]==s[j]$,那么$s[i:j]$也是回文串。

def palindrome2(s):
    n = len(s)
    dp = [[False for i in range(n)]for i in range(n)]
    for i in range(n):
        dp[i][i] = True
        dp[i][i-1] = True
    ans = 0
    for l in range(2,n+1):
        for i in range(n-l+1):
            j = i+l-1
            if dp[i+1][j-1] and s[i]==s[j]:
                dp[i][j] = True
                ans = l
    return ans    

3. 中心拓展

时间复杂度:$O(n^2)$

回文串都是以中心对称的,因此可以枚举回文串的中心,再从中心向两边拓展找出当前中心的最长子串。注意中心可以是字符,也可以是字符之间的间隙,为了方便起见,将字符串的字符之间都插入一个特殊符号便于处理,例如”ABC”变为”A_B_C“。

def palindrome3(s):
    s = "".join(map(lambda x:'_'+x,s))+'_'
    n = len(s)
    ans = 0
    for i in range(n):
        l = r = i
        while l-1 >= 0 and r+1 < n and s[l-1]==s[r+1]:
            l -= 1
            r += 1
        ans = max(ans,r-l+1)
    return ans/2

4. Manacher算法

时间复杂度:$O(n)$

Manacher算法是由Manacher在1975年提出的,算法的思想也是从左到右依次计算以当前字符为中心的最大回文串,但在计算时利用了回文子串的特殊性质来减少计算量。

假设已知$S$的两个回文子串$S1$,$S2$,其回文中心字符的位置分别为$c1$,$c2$($c1$ < $c2$,$c1$在$c2$的左侧),并且$S1$又是$S2$的子串。由于$S2$是回文串,因此$S2$中的任一子串在以$c2$为对称轴的右侧也有完全相同的子串。根据这一性质,存在$S3$为$S2$的子串,并且$S3$和$S1$完全相同并以$c2$为对称轴对称。那么$S3$也同样是回文串,其对称中心为$2*c2-c1$。并且若$S1$不是$S2$的前缀,或者$S2$是$S$的后缀的情况下,以$2*c2-c1$对称的最大回文子串可以直接确定为在$S2$中与$S1$完全对称的子串。

因此,当确定了当前中心$c1$的最大回文子串$S1$后,设其长度$l1$,向右去找在$S1$内可以直接确定的最大回文子串的对称中心,这些对称中心则可以直接跳过而不去计算。只有当回文串不能直接确定时,才需要进一步比较确定该中心的最大回文子串。

完整的算法如下:

#length[i] 表示以第i个字符为中心的最大回文串长度
1. 当前中心c = 1
2. 循环以下步骤直到c不合法:
    a. 从两端同时扩展得到以c为中心的最长回文子串,其长度为l,length[c] = l
    b. i = 1,2,..;当length[c-i]所代表的子串是length[c]的子串,且不为length[c]的前缀或者length[c]是原字符串的后缀时,length[c+i]可以直接确定为length[c-i]。即根据length[c-1],length[c-2]...的值来更新可以确定的最长回文子串长度length[c+1],length[c+2]...直到不能确定其回文长度的中心为c+i
    c. 令当前中心c = c+i

同样也需要在字符中插入特殊字符在处理中心为间隙的情况。

def palindrome4(s):
    s = "".join(map(lambda x:'_'+x,s))+'_'
    n = len(s)
    length = [0 for i in range(n)]
    c = 0
    while c < n:
        l = c-length[c]/2
        r = c+length[c]/2
        while l-1 >= 0 and r+1 < n and s[l-1]==s[r+1]:
            l -= 1
            r += 1
        length[c] = r-l+1
        i = 1
        # 能确定以c+i为中心的最长子串的长度
        while c-i >= 0 and c+i < n and c-i-length[c-i]/2>c-length[c]/2 or\
             (c-i-length[c-i]/2==c-length[c]/2 and c+length[c]/2==n-1):
            length[c+i] = length[c-i]
            i += 1
        # 不能确定以c+i为中心的最长子串的长度,但能确定其至少大于length[c-i]
        if c-i >= 0 and c+i < n and c-i-length[c-i]/2==c-length[c]/2:
            length[c+i] = length[c-i]
        c = c + i
    return max(length)/2

时间复杂度证明:

  1. 考虑内循环中字符的总比较次数,每次比较的右端字符都在前次比较过的右端字符的后面,也就是说右端字符并没有重复,而右端字符最多有$n$个位置,字符比较次数最多为$n$次
  2. 考虑内循环中确定$length[c+i]$的次数,因为$length$最多有$n$个值,确定$length[c+i]$不会重复访问,因此确定$length[c+i]$最多为$n$次。

综上,时间复杂度为$O(n)$

参考

  1. Editing Longest palindromic substring - Wikipedia, the free encyclopedia
  2. Finding the Longest Palindromic Substring in Linear Time
  3. Longest Palindrome (最长回文子串) - 夜鱼的专栏 - 博客频道 - CSDN.NET