1. 题型

• 最长回文子串
• 回文子串的个数

2. 暴力求解

枚举出所有的子串，然后再判断这些子串是否是回文。假设字符串的长度为 n。我们可以看出前者会用 $O(n^2)$ 的时间枚举出所有的子串 $s[l_i\cdots r_i]$ 然后再用 $O(r_i-l_i+1)$ 的时间检测当前的子串是否是回文，整个算法的时间复杂度是 $O(n^3)$。

3. 中心扩展算法

枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。

枚举回文中心的是 $O(n)$ 的时间复杂度，对于每个回文中心拓展的次数也是 $O(n)$ 的，所以时间复杂度是 $O(n^2)$。

简单来说就是先确定一个回文中心 mid ，然后向两边扩展，直到扩展不动了，此时窗口中的回文子串即为以 mid 为中心的最长回文子串（最长回文子串）。

同时，确定中心后那个中心即为一个回文子串，每次扩展都会形成一个新的回文子串（回文子串的个数）。

在实现的时候，我们需要处理一个问题，即如何有序地枚举所有可能的回文中心，我们需要考虑回文长度是奇数和回文长度是偶数的两种情况。如果回文长度是奇数，那么回文中心是一个字符；如果回文长度是偶数，那么中心是两个字符。当然你可以做两次循环来分别枚举奇数长度和偶数长度的回文，但是我们也可以用一个循环搞定。我们不妨写一组出来观察观察，假设 n=4，我们可以把可能的回文中心列出来：

由此我们可以看出长度为 n 的字符串会生成 2n−1 组回文中心 $[l_i,r_i]$，其中 l = i // 2，r = i // 2 + i % 2 （//表示计算完除法向下取整）

例题1：求回文子串的个数

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。示例 1：输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解：

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)res = 0for i in range(2 * n - 1):l = i // 2r = i // 2 + i % 2while 0 <= l and r < n and s[l] == s[r]:l -= 1r += 1res += 1return res

4. 马拉车算法（Manacher算法）

这个算法将解决回文子串的时间复杂度被提升为 $O(n)$。

这是一个奇妙的算法，是1957年一个叫Manacher的人发明的，所以叫Manacher‘s Algorithm,主要是用来查找一个字符串的最长回文子串，这个算法最大的贡献是将时间复杂度提升到线性，前面我们说的动态规划的时间复杂度为 O(n²)。

前面说的中心拓展法，中心可能是字符也可能是字符的间隙，这样如果有 n 个字符，就有 n+n+1 个中心：

为了解决上面说的中心可能是间隙的问题，我们往每个字符间隙插入 “#”,为了让拓展结束边界更加清晰，左边的边界插入 “^” ,右边的边界插入 “$”:

S 表示插入"#", “^” , "$"等符号之后的字符串，我们用一个数组P表示S中每一个字符能够往两边拓展的长度:

比如 P[8] = 3，表示可以往两边分别拓展3个字符,也就是回文串的长度为 3，去掉 # 之后的字符串为 “aca” ：

P[11]= 4，表示可以往两边分别拓展4个字符，也就是回文串的长度为 4，去掉 # 之后的字符串为 “caac” ：

假设我们已经得知数组P，那么我们怎么得到回文串？

用 P 的下标 index ，减去P[i]（也就是回文串的半径），可以得到回文串开头字符在拓展后的字符串 S 中的下标，除以2，就可以得到在原字符串中的下标了。

那么现在的问题是：如何求解数组P[i]

其实,马拉车算法的关键是：它充分利用了回文串的对称性，用已有的结果来帮助计算后续的结果。

假设已经计算出字符索引位置 P 的最大回文串，左边界是P_L，右边界是P_R：

那么当我们求位置 i 的值 P[i] 的时候，如果 i 小于等于 P_R,其实我们可以找到 i 关于 P 的对称点 j ：

那么假设 j 为中心的最长回文串长度为 len，并且在 P_L 到 P 的范围内，则 i 为中心的最长回文串也是如此：以 i 为中心的最长回文子串长度等于以 j 为中心的最长回文子串的长度

但是这里有两个问题：

前一个回文字符串P，是哪一个？
有哪些特殊情况？特殊情况怎么处理？
(1) 前一个回文字符串 P，是指的前面计算出来的右边界最靠右的回文串，因为这样它最可能覆盖我们现在要计算的 i 为中心的索引，可以尽量重用之前的结果的对称性。

也正因为如此，我们在计算的时候，需要不断保存更新 P 的中心和右边界，用于每一次计算。

(2) 特殊情况其实就是当前 i 的最长回文字符串计算不能再利用 P 点的对称，包括以下两种情况：

一是以 i 为中心的回文串的右边界超出了 P 的右边界 P_R

这种情况的解决方案是：超过的部分，需要按照中心拓展法来一一拓展。

二是i 不在 以 P 为中心的回文串里面，只能按照中心拓展法来处理

至于算法的复杂度，空间复杂度借助了大小为n的数组，为O(n)，而时间复杂度，看似是用了两层循环，实则不是 O(n²)，而是 O(n)，因为绝大多数索引位置会直接利用前面的结果以及对称性获得结果，常数次就可以得到结果，而那些需要中心拓展的，是因为超出前面结果覆盖的范围，才需要拓展，拓展所得的结果，有利于下一个索引位置的计算，因此拓展实际上较少。

实现1：求回文子串的个数

import mathclass Solution:def preProcess(self, s, n):if n == 0:return "^$"ret = "^"for i in range(n):ret += "#" + s[i]ret += "#$"return retdef countSubstrings(self, s: str) -> int:n = len(s)S = self.preProcess(s, n)N = len(S)p = [0] * Ncenter, right = 0, 0res = 0for i in range(1, N-1):j = 2 * center - iif right > i:p[i] = min(p[j], right - i)else:p[i] = 0# 中心扩展，已经确定[i-p[i], i+p[i]]内的子串为回文串了while S[i + p[i] + 1] == S[i - p[i] - 1]:p[i] += 1if i + p[i] > right:center = iright = i + p[i]# 因为在字符串里面插入了#，所以需要除以2# 比如其中的一个回文子串为 "#a#b#c#b#a#"，这种情况下p[index_c] = 5# 实际包含的子串为："c", "bcb", "abcba", 5 / 2 向上取整为3res += math.ceil(p[i] / 2)return ress = "abccb"
solution = Solution()
print(solution.countSubstrings(s))

实现2：求最长回文子串

def preProcess(s):n = len(s)if n == 0:return "^$"ret = "^"for i in range(n):ret += "#" + s[i]ret += "#$"return retdef longestPalindrome(str):S = preProcess(str)n = len(S)# 用于保存回文串的半径P = [0]*n# 用于保存边界最右的回文中心以及右边界center = 0right = 0# 从第 1 个字符开始for i in range(1, n-1):# 找出i关于前面中心的对称，i+j=2*centerj = 2 * center - iif right > i:# i 在右边界的范围内，看看i的对称点的回文串长度，以及i到右边界的长度，取两个较小的那个# 不能溢出之前的边界，否则就得中心拓展P[i] = min(right - i, P[j])else:# 超过范围了，中心拓展P[i] = 0# 中心拓展while S[i + 1 + P[i]] == S[i - 1 - P[i]]:P[i] += 1# 看看新的索引是不是比之前保存的最右边界的回文串还要靠右if i + P[i] > right:# 更新中心center = i# 更新右边界right = i + P[i]# 通过回文长度数组找出最长的回文串maxLen = 0centerIndex = 0for i in range(1, n-1):if P[i] > maxLen:maxLen = P[i]centerIndex = istart = (centerIndex - maxLen) // 2return str[start: start + maxLen]

参考：马拉车算法，其实并不难!!!