LeetCode 647: 回文子串

给你一个字符串s，请你统计并返回这个字符串中回文子串的数目。

回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符构成，也会被视作不同的子串。

解法一：暴力求解

暴力求解的思路很简单，只要找到字符串所有的子串并判断其是否为回文字符串即可，有两种可行方法。

方法一：枚举法

使用双重循环枚举所有子串，例如"abcd"可以依次遍历"a"、"ab"、"abc"、"abcd"、"b"、"bc"、"bcd"、"c"、"cd"、"d"。然后，判断每个子串是否为回文字符串。判断时使用头尾两个指针，依次比较头尾指针指向的字符是否相等，如果相等，头指针向后移动，尾指针向前移动，直到相遇。

时间复杂度：

空间复杂度：

首先枚举所有字符串需要的复杂度，判断是否为回文字符串最坏复杂度为，因此总的时间复杂度为。

参考代码：

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

def isPalindromic(s: str, head: int, rear: int) -> bool:
            while head < rear:
                if s[head] == s[rear]:
                    head += 1
                    rear -= 1
                else:
                 return False
            return True

cnt = len(s)
        for head in range(len(s)):
            for rear in range(head+1, len(s)):
                if isPalindromic(s, head, rear):
                    cnt += 1
        return cnt

方法二：中心扩展法

我们注意到，回文字符串都是对称的。因此，我们可以从一个给定的中心开始向外扩展，找到以该位置为中心的最大扩展半径，即可得到以该位置为中心的回文子串的数量。

时间复杂度：

空间复杂度：

由于需要需要考虑奇数长度的回文字符串——中心为一个字符，以及偶数长度的回文字符串——中心在中间的两个字符之间，我们将其也看作是一个特殊的、从未在给定的字符串中出现过的字符，所以需要遍历2n+1个回文中心。对于每个回文中心，最多扩展n步，因此需要的时间复杂度为。

参考代码：

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

def getR(s: str, left: int, right: int, s_len: int) -> bool:
            R = 0
            while left >= 0 and right < s_len and s[left] == s[right]:
                R += 1
                left -= 1
                right += 1
            return R

cnt = 0
        s_len = len(s)
        for i in range(len(s)):
            cnt += getR(s, i, i, s_len)
            cnt += getR(s, i, i+1, s_len)
        return cnt

解法二：Manacher算法

Manacher算法一定程度上也属于动态规划，它充分利用了已经得到的回文子串的信息。对于一般的查找回文子串的方法，需要考虑奇数长度的回文字符串——中心为一个字符，以及偶数长度的回文字符串——中心在中间的两个字符之间。

例如，对于上图中的字符串"abaaba"，所有竖线看作是两个字符中间的位置，加上原来的六个字符，共13个位置。对每个位置赋予一个值，表示在原字符串以该位置为中心的最长回文子串（Longest Palindromic Substring，LPS）的长度。比如，Position=3处，L[3]=3，表示以"b"为中心的LPS长度为3，即字符串"aba"，Position=6处，L[6]=6，表示以两个"a"中间位置为中心的LPS长度为6，即字符串"abaaba"。

同时，我们观察可以发现Position值的另一层含义——最长回文半径，或者说，以该位置为中心的LPS向两边延展的步数。同样，Position=3处，以"b"为中心分别向左右两侧各走三步，得到"|a|b|a|"；Position=6处，以"|"为中心分别向左右各走六步，得到"|a|b|a|a|b|a|"。

因此，如果可以求出数组L，既可以求出最长回文子串，也可以通过求和得到给定字符串的回文子串的数量。

通过上面的分析可以看出，求出数组L即可解决问题。如果在每个位置中心扩展求值，则与暴力法的算法无异，因此，要考虑如何降低复杂度。

仍然以该图为例，观察可以看出：L[3]=L[9]=3、L[4]=L[8]=0、L[5]=L[7]=1。由于L[6]=6，L[4]=0，L[5]=1，也就是以Position 4和5为中心的短LPS是包含在以Position 6为中心的长LPS内的，因此可以直接得出L[8]=0，L[7]=1，而不必通过中心扩展的方法求解。

但情况并不总是如此，因此需要分析在哪些情况下可以应用该规律，哪些情况下需要特殊处理。

将字符串抽象为下图：

当前需要求解的是以 位置为中心的LPS长度。

• 从左至右遍历Position: 0...2n。在求解过程中，假设遍历到 ，在求解L[i]时尽量使用到 左侧已知点的信息。

• 假设在 左侧有一点C，其右边界为Center right position，记为R，有R=C+L[C]；其左边界为Center left position，记为R'，有R'=C-L[C]。为了充分利用已知信息，C需要保证在 左侧的所有点中，C右边界最大/最靠右。

• 关于C的对称点为 ，L[i']已知。

那么，在什么情况下可以使用上述的规律L[i]=L[i']呢？

• 当 时， 和 超出了C点LPS边界，无法使用上述规律，只能以中心扩展方式计算。

• • ，即 点LPS包围在C点LPS中，并且 点LPS左端在C点LPS左端的右侧，此时 点的LPS必然与 点LPS完全一致，即理想情况，此时L[i]=L[i']；

  • ，即 点LPS包围在C点LPS中，但是 点LPS左端与C点LPS左端重叠， 点扩展到R'，根据对称性， 点也至少扩展到R，但是再向外则无法确定，需要使用中心扩展计算，不过只需从R处开始即可；

  • ，即 点LPS超出了C点LPS的范围，此时L[i]=R-i，即 点右边界为R。原因是：假设 可以扩展到R右侧，考虑R+1，那么R+1关于 对称的点 m 必然在C的LPS内，并且 m 关于C的对称点 n 关于 的对称点为 R'-1，此时有 R'-1、n、m 和 R+1 这几个位置上对应的字符相同，而 R'-1 和 R+1 位置上字符相同与C点的LPS相悖。

    举个🌰：

    考虑字符串"cabacdcabae"，为了更明晰一点插入两个分隔符："cabac|d|cabae"，假设当前要求的为右侧"b"字符的LPS，对应的C为中间的"d"，其LPS为"abac|d|cacb"，对称点为左侧"b"，其LPS为"cabac"，满足 即 的情况，此时 即为 "aba"。

写成伪代码如下：

if i > R:
	L[i] = 0
	从位置 i 逐步扩展求L[i]
else:
	if L[i'] < R-i:
		L[i] = L[i']
	else if L[i'] = R-i:
		L[i] = L[i']
		从 R 处开始扩展求 L[i]
	else:
		L[i] = R-i

从上文分析可以知道，算法依赖于位置C，那么要如何更新C呢？

当需要扩展时，C的位置可能会发生改变，有两种情况下会发生扩展：(i>R) || (i<=R && L[i']==R-i)。位置C表示 左侧的点中，右边界最大的点，这样能够尽可能减少扩展的步数。所以，当 的LPS超过R时，将C更新为 ，并将R更新为 的右边界。

Manacher算法是线性时间复杂度，即。

在上文的伪代码外层还套着一个循环，从左向右遍历Position，其复杂度为。对于循环内部，有一个扩展法的子循环，该子循环在整个程序中可以看作是逐步更新C和扩展C右边界R的过程，R最大为2n（字符+空隙位置），所以在整个程序中子循环执行总次数为级别。因此，Manacher算法整体时间复杂度为。

空间复杂度为，即L数组需要的额外空间。

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

def Manacher(s: str) -> list:
            s_ex = '#' + '#'.join(list(s)) + '#'
            s_len = len(s_ex)
            L = [0] * s_len
            center = right = 0
            for i in range(1, s_len-1):
                i_mirror = 2 * center - i
                if i > right:
                    L[i] = 0
                    while (i-L[i]-1 >= 0 and i+L[i]+1 < s_len and s_ex[i-L[i]-1] == s_ex[i+L[i]+1]):
                        L[i] += 1
                else:
                    if L[i_mirror] < right - i:
                        L[i] = L[i_mirror]
                    elif L[i_mirror] == right - i:
                        L[i] = L[i_mirror]
                        while (i-L[i]-1 >= 0 and i+L[i]+1 < s_len and s_ex[i-L[i]-1] == s_ex[i+L[i]+1]):
                            L[i] += 1
                    else:
                        L[i] = right - i
                if i + L[i] > right:
                    center = i
                    right = i + L[i]
            return L

L = Manacher(s)
        return sum([(i+1)//2 for i in L])

根据Reference[1]中进行分支优化后的代码如下：

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

def Manacher(s: str) -> list:
            s_ex = '#' + '#'.join(list(s)) + '#'
            s_len = len(s_ex)
            L = [0] * s_len
            C = R = 0
            for i in range(1, s_len-1):
                i_mirror = 2 * C - i
                if i < R:
                    L[i] = min(L[i], R-i)

while (i-L[i]-1 >= 0 and i+L[i]+1 < s_len and s_ex[i-L[i]-1] == s_ex[i+L[i]+1]):
                    L[i] += 1

if i + L[i] > R:
                    C = i
                    R = i + L[i]
            return L

L = Manacher(s)
        return sum([(i+1)//2 for i in L])

但是分支优化后的代码在LeetCode上的执行时间反而比未优化的长很多：

不清楚是否是数据分布不均匀，分支优化后的代码在LeetCode上的执行时间反而比未优化的慢6～7倍，而的中心扩展法还要比分支优化后的Manacher快3倍😂。

References:

[1] 有什么浅显易懂的Manacher Algorithm讲解？

[2] Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 1

[3] Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 2

[4] Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 3

[5] Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 4