LongestPalindromicSubstring

发表于 | 分类于 |
字数统计: 3,026

本文主要是介绍利用动态规划与Manacher 算法求解最长回文子串，LeetCode链接

动态规划

问题分析

对于最长回文子串的求解可以抽象为一个动态规划的多阶段决策过程。例如，对于对于字符串S”ababa”回文判断，如果我们知道该回文字符串的子串s”bab”为回文字符串的话，那么显然对于字符串S的判断，只需要判断S左右两端字符是否一致即可。若S左右两端的字符相同，则在s为回文串的前提下，S为回文字符串；若两端字符不相同，则S不是回文字符串。

多阶段决策过程抽象

基于上述的问题分析，假设需要判断的字符串S[i:j]是否为回文串，那么该决策过程可以分解为两步，首先判断子串S[i+1:j-1]是否为回文串，若不是，则S串不是回文字符串；若该子串是回文串，且S[i]等于S[j]，则S为回文字符串。因此，对于任一字符串S[i:j]，我们可以定义二维数组P表示该字符串状态，其中$i < j$：

基于上述二维数组，可以定义如下状态转移方程：

上述状态转移方程表示的含义即为$P(i,j)$为true的条件为$P(i+1,j-1)$为真（即S[i+1,j-1]为回文串）且S[i]字符与S[j]字符相等。
由于上述状态转移方程之中，必须要求$ i \leq j $ 且 $ i +1 \leq j - 1 $，所以，需要先初始化$i = j $和$ i + 1 = j $的情况，其中$ P[i,i] $初始化为true，$ P[i, i + 1] $依据字符串的实际情况进行。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        #采用动态规划的方法
        DPMa = [[0 for i in range(len(s))] for j in range(len(s))]  #初始化二维矩阵，用户动态规划预计算

        LenPa = 1
        iMax = jMax = 0
        for i in range(len(s)):
            DPMa[i][i] = 1
            if i + 1 < len(s) and s[i] == s[i + 1]:#出现相同两位的回文字符串
                DPMa[i][i + 1] = 1
                LenPa = 2
                iMax = i
                jMax = i + 1
        for k in range(2, len(s)):
            for i in range(0, len(s) - k):
                j = i + k
                if DPMa[i + 1][j - 1] and s[i] == s[j]:
                    DPMa[i][j] = 1
                    if k + 1 > LenPa:
                        LenPa = k + 1
                        iMax = i
                        jMax = j

        return s[iMax:jMax + 1]

时间复杂度与空间复杂度

时间复杂度：由上述代码实现可以看出，动态规划过程为两重循环，因此时间复杂度为$O(n^2)$
空间复杂度：使用了二维数组保存个子串状态，空间复杂度为$O(n^2)$

Manacher 算法

利用动态规划解决最长回文子串问题需要 $O(n^2)$ 的时间复杂度，但对于该问题有一种称之为Manacher算法的，$O(n)$的解决方法。以下主要是对LeetCode上关于该算法文章进行翻译
、整理而成的（原文）

Note

这是“最长回文子串”的第二部分。在这篇文章中，我们将分析一个能再线性时间内解决最长回文子串的算法——Manacher算法。在之前的LeetCode的solution中给出了四种不同求解最长回文子串的方法，最简单的算法时间复杂度为$O(n^2)$，空间复杂度为常数级。本文介绍的Manacher算法的时间复杂度和空间复杂度都为O(n).

Hint

考虑在之前的解决算法之中出现的最坏情况，即输入字符串是多个回文字符串重叠而成的情况。例如，输入字符串是”aaaaaaaa”和”cabcbabcbabcba”。对于出现的这种最坏情况，我们可以利用回文字符串的对称性来避免一些不必要的重复计算。

An O(N) Solution (Manacher’s Algorithm):

首先我们需要对输入的字符串进行处理，处理方式为：对输入字符串S，在首尾以及每个字符之插入特殊字符’#’。

例：S=”abaaba”，处理完毕后 T=”#a#b#a#a#b#a#”
S为输入原始字符串，T为预处理后的字符串。
$S_i$表示S的第i位置的字符，$T_i$表示T的第i位置的字符

经过这样的处理，可以对输入的字符串进行统一化处理。在完成插入操作之后，不论输入的字符串长度是偶数还是奇数，在处理后，字符串长度都将变成奇数长度，并且原字符串中各字符的相对位置不变。

为了找出最长回文子串，我们可以对每一个$Ti$进行如$T(i-d)…T_(i+d)$的扩展来组成一个回文字符串。对于这种扩展，你可以立即看到，d就是以$T_i$为中心扩展而成的回文字符串的长度(这个长度减去了特殊字符’#’的长度))。

我们需要定义一个存储中间结果的数组P，中间数组$P[i]$存储的是以$T_i$为中心的回文字符串的长度。因此，在P数组计算完成之后，最长回文字符子串的中心点索引就是数组P中最大值的索引。
对于上述例子，我们可以从左到右手动计算数组P的值，结果如下：

T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

从上述数组P的值中可以看出，P[6]为6，具有最大值，该索引值对应字符子串是”abaaba”，由原始输入字符串可知，该字符串即为最长回文子串。

若是在回文字符串”abaaba”画一条中轴线，可以看到P数组的值将根据该中轴线对称分布。这不仅仅是这一个回文串的性质，对于任意一回文串，都具有该对称性质。

根据以上性质，让我们考虑一个更加复杂的、具有回文串叠加的字符串S=”babcbabcbaccba”。

上图展示了S字符串在完成特殊插入之后的字符串T。现在先假定你已经到达了P数组被部分完成的状态。实心中轴线表示回文子串”abcbabcba”的中点，两条虚线严格表示该回文串的边界，L和R表示左右边界索引值。基于该中轴线，索引i的镜像位置的索引表示$i^,$。那么接下来的问题是，如何计算数组元素$P[i]$的值？

假定我们当前需要计算的是当索引为$P[13]$的值。首先我们可以观察其基于以C为中心的回文子串的镜像位置$i^,$索引表示的值。针对$i=13$，其镜像对称位置$i^,$为9。

上图两条绿色的实线表示的是以$i$和$i^,$为中心表示的回文串的覆盖范围。我们可以看到i的镜像位置是$i^,$，$P[i^,]=P[9]=1$。由上图回文字符串基于中心的对称性可知，可以清楚的看到$P[i]=P[13]$的值也是1。

正如之前看到的，由于回文字符串的对称性，$P[i^,]=P[i]=1$显然是正确的。事实上，在上述字符串T中，位于中心点之后的三个元素都符合对称性的要求，即有$P[12]=P[10]=0, P[13]=P[9]=1, P[14]=P[8]=0$。

现在需要考虑的问题是，当i为15时，基于C的镜像位置$i^,=7$，那么是否有$P[15]=P[7]=7$呢？

现在需要考虑索引为15的时候，$P[i]$的值是多少？如果考虑对称性的话，$P[i]$的值应该与$P[i^,]$的值相同，都为7。但从上图中可以看出，显然这个是不成立的。如果我们以$T_15$为中心进行回文字符串的扩展，将可以组成回文串”a#b#c#b#a”，这个回文串显然是比对称性所计算出来的回文串要小。因此，接下来需要考虑为什么会出现这种情况。

在上图之中，绿色实线表示的区域是以C为中心基于对称性的边界范围。红色的实线表示的是以C为中心对称性不匹配的区域，即不是回文串的部分。绿色的虚线表示的区域是跨越中心的部分。

从上图中，以$i^,=7$以及$i=15$为中心的子串在绿色实线区域内是匹配的非常好的。在穿越中心的部分（绿色虚线部分）也是非常完整的复合对称性的要求。仔细观察可以发现，$P[i^,]=7$，而却其扩展一直延伸穿过了回文字符串的左边缘（直到红色实线部分），红色实线部分就不在属于以C为中心的回文对称性质部分。针对上述$i=15$时，当$P[i]>5$时，我们可以知道，要找出其准确的$P[i]$值，必须对边界R之外的字符串进行格外的匹配。在本例中，因为$P[21] \not= P[1]$，我们可以得出结论，$P[i]=5$。

上述算法要点：

上述算法要点，原文关于else的赋值给错了，原文是$P[i] \geq P[i^,]$，应修改为上述表达，表示当前索引串的右边界必定会大于当前右边界

上述步骤就是整个Manacher 算法的核心步骤以及本质。基于上述算法过程，接下来剩下的步骤就是确定我们应该在什么是时候向右移动中心点以及对应的边界R。相比之前的分析，这个问题是非常简单的，移动方式如下：

如果以i为中心的回文串的扩展越过了当前右边界R，我们将更新中心点C为i（即新的回文串的中心），并且我们将边界R扩展到新的回文串的右边界。

从上述算法中可以看出，每一个步骤都存在两种情况：如果$P[i] \leq R - i$，则只有$P[i] = P[i^,]$ 这一个步骤；其他一种情况是，我们需要尝试对右边界进行扩展，并将回文字符串的中心修改为i。扩展右边界R（内部循环完成）最多将花费N步完成（N表示输入字符串的长度），每一个中心点的定位和测试总计将花费N步。因此，这个算法将保证能在最多$2*N$步内完成。因此，该算法的时间复杂度就是O(n)。

python实现

原文之中给出了java代码实现，以下是依据该代码的python实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def longestPalindrome(self, s):
        s = Solution.PreProcess(s)  #预处理
        P = [0] * (len(s))  #p数组，保存回文长度
        C = 0   #中心点位置，初始化为0
        R = 0   #右边界位置，初始化为0
        for i in range(1, len(s) - 1):
            iMirror = 2*C - i
            if iMirror < 0:
                iMirror = 0
            # 计算在当前以C为中心的的最大对称位置
            P[i] = min(R - i, P[iMirror]) if R > i else 0
            # 对边界进行扩展，利用循环对边界进行扩展
            while (s[i - 1 - P[i]] == s[i + 1 + P[i]]):
                P[i] += 1
            # 计算新的C和R的位置
            if (i + P[i] > R):
                R = i + P[i]
                C = i

        MaxLen = max(P)
        index = P.index(MaxLen)
        return s[index - MaxLen: index + MaxLen + 1].replace('#', '')


    def PreProcess(s):
       """
       预处理过程，在字符串收尾插入^$ ，在字符串间插入#
       :param s: 待处理字符串
       :return: 处理完成的字符串
       """
       sList = list('^' + s + '$')
       return '#'.join(sList)

参考

[1] https://articles.leetcode.com/longest-palindromic-substring-part-ii/