最长回文串算法

时间:2021-03-12 18:41:43

总的来说,最长回文串算法分为以下几种。

暴力法

通过遍历整个字符串来说实现对最长回文串的查找
首先一个字符串所有子串,个数为n2个,然后逐个判断遍历即可,算法复杂度O(n3)
代码如下:

def is_palindrome(s):
    str_length = len(s)

    for i in range(str_length / 2):
        if s[i] != s[str_length - 1 - i]:
            return False

    return True

# 暴力求解法
def algorithm1(s):
    length = len(s)

    for i in range(length):
        for j in range(i + 1):
            if is_palindrome(s[j: length - i + j]):
                return len(s[j: length - i + j])

    return 1

动态规划

中心扩展法

该算法感觉是Manacher算法的前身吧,使用字符中心向两侧扩展,这样,只需要进行遍历字符串一次,然后针对每个字符进行单独的判断即可。
代码如下:


def change(s):
    l = []
    for c in s:
        l.append(c)

    return "@#%s#" % "#".join(l)

# 中心求解法
def algorithm3(s):
    s = change(s)
    flag = 0
    for i in range(2, len(s) - 2):
        temp = 1
        while s[i - temp] == s[i + temp]:
            temp += 1

        if temp > flag:
            flag = temp

    return flag - 1

其实中心求解法完全可以不修改字符串,不过那样处理起来比较麻烦,代码写起来费力一些。

Manacher算法

这是一个比较牛掰的算法,其实感觉是对中心扩展法的优化,但是我搞了好久才大体搞明白,主要因为其中有几个难点

  • 需要对字符串进行变换
  • 针对辅助数组的使用优化计算比较难理解
  • 算法复杂度分析

这个方法的牛掰之处就在于它的算法复杂度是O(n)的,想出暴力解法很简单,但是直观来看,算法复杂度差太多了。

字符串变换

因为Manacher有个核心定义,叫做P[i]
p[i] : 以i为中心的的回文半径长度
因为该数组,所以必须对字符串进行变换。因为当且仅当回文为奇数长度字符串,才可能存在P[i]这种定义

辅助数组优化计算

python实现的代码如下:

def change(s):
    l = []
    for c in s:
        l.append(c)

    return "@#%s#" % "#".join(l)

# Manacher算法
def algorithm4(s):
    s = change(s)
    p = [0] * len(s)
    index = 0
    for i in range(2, len(s) - 2):
        if p[index] + index > i:
            p[i] = min(p[2 * index - i], p[index] + index - i)
        else:
            p[i] = 1

        while s[i - p[i]] == s[i + p[i]]:
            p[i] += 1

        if index + p[index] < i + p[i]:
            index = i

    return max(p) - 1

其中有个判断,为 p[index] + index > i
其代表的意思可以结合P数组的概念进行理解, p[index]为以index为中心的回文半径长度,index为其索引值,
所以 p[index] + index的意思为以index为核心的回文辐射范围
if p[index] + index > i:说明下一个遍历点,在以index为核心的回文辐射范围之内,既然在辐射范围之内,说明p的起始计算位置至少要从p[2 * index -i],或者p[index] + index - i开始。
这里比较绕。
这里解释一下

  • p[2 * index - i]:因为 2 * index - i 和 i 关于 index是对称的,而根据回文本身的特点,我们就知道 p[i] >= p[2 * index - i]
  • p[index] + index - i:这个值由其实由辐射范围去掉了i。

两者的概念很类似,其实主要就是看对称点的,根据对称点p[2 * index - i],如果该值超过了p[index]的辐射范围,那么就取值p[index] + index -i,否则就取值本身。
说起来比较绕,其实自己画个图发现这个还是比较容易理解的。

算法复杂度分析

这个算法在我看来,是比之前中心算法的一个优化,但是我一点都看不出来为什么该算法的复杂度为O(n),后来看了很多别人的讲解。
manacher算法只需要线性扫描一遍预处理后的字符串。
经过优化后,p是求解过程中,对字符串的每个字符,扫描最多只会2次,时间复杂度必然为O(n)