算法总结-回文串
回文串是是正向和反向读取相同的字符串，比如 "aba", "bb"，都是回文串。检查一个串是否是回文串可以直接判断字符串和它的反向字符串是否相等，或者从两端向中心循环依次比较。这个思想比较简单。
经典题目，LeetCode 5. 最长回文子串。暴力的解法是对每一个子串进行依次检查，看是否是回文串，然后保存最长的结果。这样时间复杂度是 $O(n^3)$ 。
第一种做法是中心扩展法，遍历每一个位置，然后从当前位置向两边扩展，这样的时间复杂度是 $O(n^2)$ ，但是有一个比较特殊的情况是偶数长度的回文串，如 "bb" ，它的中心不明确，常用的解决办法是插入特殊字符，如 #b#b# ，这样回文的长度会被处理成奇数，也就方便从中心扩展了；另外一种解决办法是，把连续的相同字符当作中心，代码如下：
class Solution_5:
def longestPalindrome(self, s: str) -> str:
# 中心扩展法
max_len = st = i = 0
while i < len(s):
j = i + 1
while j < len(s) and s[j-1] == s[j]: # 处理"bb", "bbb" 这种情况
j += 1
left = i
right = j - 1
while left > 0 and right < len(s) - 1 and s[left-1] == s[right+1]:
left -= 1
right += 1
i = j
if right - left + 1 > max_len:
max_len = right - left + 1
st = left
return s[st:st+max_len]
第二种做法，是将其转换为 LCS 问题，因为回文串的正序和逆序是相同，那么我们就可以把求最长回文串变成求 s 和 t = s[::-1] 的最长公共子序列的问题。需要注意的是，串 s 中可能包含非回文，但是逆序部分也有相同的子串，比如 "aacdefcaa", 这个用 LCS 求出来的结果是 "aac" or "caa" 显然这不是回文，所以我们需要另外判断 LCS 找出的子串是否为回文串。
注意一个回文子串在 s 中的起始位置对应到翻转后的 t 中的终止位置。这样我们把找到的一个公共子串的下标，计算对应到 s 中的起始下标 sb ，和对应到 t 中的终止下标 te, 然后我们把 te 对应到翻转前的下标，即 len(s) - te - 1 这样，如果 len(s) - te - 1 == sb , 那么这个公共子串是一个回文串。代码如下。
class Solution_5:
def longestPalindrome(self, s: str) -> str:
# 转换为 s 和 s[::-1] 的 LCS 问题
t = s[::-1]
n = len(s)
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
m, ms = 0, ''
for i in range(1, n+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > m:
# 当前最长公共子串的在字符串 s 中的终止点是当前下标 i-1, 起始点是：
# (i-1) - dp[i][j] + 1 = i - dp[i][j]
# 在 t 中终止点是 j-1, 对应到翻转前的下标应该是
# n - 1 - (j-1) = n - j
# 如果 i - dp[i][j] == n - j, 那么这一部分公共子串的首尾就是相同的，也即是回文串
if i - dp[i][j] == n - j:
m = dp[i][j]
ms = s[i-m:i]
return ms
第三种做法是直接 DP 的方法, 对于回文串 "aba" ，显然 "xabax" 也是回文串，于是我们有：
初始值为：
\[\begin{aligned} dp(i, i) &= 1 \\ dp(i, i+1) &= s[i] == s[i+1] \end{aligned}\]于是可以直接写出 DP 代码如下：
class Solution_5:
def longestPalindrome(self, s):
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
st, ed = 0, 0
for i in range(len(s)):
dp[i][i] = 1
for j in range(i - 1, -1, -1):
if j + 1 == i:
dp[j][i] = (s[j] == s[i])
else:
dp[j][i] = dp[j + 1][i - 1] and (s[j] == s[i])
if dp[j][i] and (i - j + 1) > (ed - st + 1):
st = j
ed = i
return s[st:ed + 1]
第四种做法，也即是这次要重点讲的算法：manacher 算法，这个算法中文名叫马拉车算法233333。这个算法能够充分利用回文串的特性，在 $O(n)$ 时间内找到最长回文串。
我们来重定义一下整个问题：给定一个字符串 s ，其长度为 n = len(s)，求最长回文子串。
首先，我们对字符串进行预处理，这字符中间以及开头和结尾插入不会在 s 中出现的字符，比如字符 '#' 。然后在字符串开头和结尾插入两个不同的且不在 s 中出现的字符，比如 '^' 和 '$'（这可以带来一点编程的遍历）。经过这一步处理后，字符串的长度变为 2n+3 ，是个奇数，记处理后的字符串为 ma 。
我们使用一个数组 p, p[i] 表示以 i 位置字符为中心，字符串 ma 的回文子串的半径。（因为恰好填充了一倍 '#' 字符的缘故，p[i] 的值恰好对应删去预处理插入的字符后原字符串 s 的回文子串的长度），我们的目的就是求出数组 p 。而且要在 $O(n)$ 时间内求出 p , 这个时候就要借用 DP 的思想，利用已经计算过的 p[j]，其中 (j < i) 来计算 p[i] ，因此，我们需要在计算 p[i] 之前，先计算出所有 p[j] 的值。
我们使用 mx 表示 0 + p[0] 到 i-1 + p[i-1] 的最大值，即当前向右匹配到的最右的位置，用 cid 表示 mx 对应的的中心位置。也即是有：cid + p[cid] == mx。接下来是算法了核心，也是 $O(n)$ 时间复杂度的保证。
设 j 是 i 关于 cid 的对称位置（即 i, j 到 cid 的距离相同），如 -----j---cid---i----这种形式。现在我们要在已知，p[j]，cid, p[cid] , mx 的情况下，求出 p[i]。这对应两种情况：
mx <= i, 即mx在i的左边，--j-mx'--cid--mx-i----，那就只能暴力从i向两边扩展求p[i]的长度mx > i, 即mx在i的右边，--mx'--j---cid---i--mx--，显然以cid为中心的回文子串包括了i位置。写的清楚一点就是有ma[j] == ma[i], ma[j-1] == ma[i+1], ..., ma[mx'] == ma[mx]。而以i为中心的回文子串与以j为中心的回文子串有关，因此，我们得到了一个p[i]的下界p[i] >= p[j]，如果p[j] + i > mx而以i为中心，超过mx的部分是为检查过的，因此另一个下界是mx - i，中和起来，p[i] = min(p[j], mx-i)，然后在此基础上向两边扩展。
而对于 j ，根据与 i 关于 cid 对称可以得到 j = cid - (i - cid) = 2 * cid - i 。
综合上述，我们就可以写出 manacher 算法的代码了。
class Solution_5:
def longestPalindrome(self, s):
def manacher(s):
ma = '^#' + '#'.join(s) + '#$' # 预处理 长度会变成2n-1+4 = 2(n+1) + 1 奇数
p = [0] * len(ma) # 要计算的数组p
cid = 0
mx = 0
max_len = 0
max_idx = 0
# 循环从1~len-1, 第0个字符和最后一个字符，'^'和 '$'不会有回文子串，
# 忽略头尾这两个字符可保证扩展时不检查边界也不会越界。
for i in range(1, len(ma) - 1):
if mx > i: # mx在i的右边
p[i] = min(p[2 * cid - i], mx - i)
else: # mx在i的左边
p[i] = 1
# 暴力的向两边扩展，注意这里我们并没有检查边界，因为设定了不相等
# 的字符'^'和 '$'，确保了在遇到边界一定会出现不等而退出循环,
# 这是为什么使用两个不同的字符的原因，bonus~
while ma[i + p[i]] == ma[i - p[i]]:
p[i] += 1
if i + p[i] > mx:
mx = p[i] + i # 更新 mx 和 cid
cid = i
if p[i] > max_len:
max_len = p[i]
max_idx = i
# 映射回原来的字符串中，起始点是最长的回文串的中心的减去长度 // 2，
# 长度是 max_len - 1(如果半径不算中心的话，那就是max_len)
st = (max_idx - max_len)//2
return s[st: st+max_len-1]
return manacher(s)
LeetCode 647. 找出一个字符串中回文子串的数目。同样可以使用中心扩展法。算上两个字符中间的空，总共有 2N-1 个位置，检查以这些位置为中心点对称的字符串是否为回文串。检查的时候同时向两端扩展就可以了。唯一值得注意的是，偶数位置是指向原字符串的字符，奇数位置指向的两个字符中间的位置。
class Solution_647:
def countSubstrings(self, s: str) -> int:
# expand to both sides
# 例子
# a # b # b # a # c
# index: 0 1 2 3 4 5 6 7 8
n = len(s)
res = 0
for idx in range(2 * n - 1):
lo = idx // 2
hi = (idx + 1) // 2 # 奇数位置是两个字符中间，所以hi指向右边字符
while lo >= 0 and hi < n and s[lo] == s[hi]:
lo -= 1
hi += 1
res += 1
return res
也可以使用 DP 方法。我们用 dp(i, j) 表示 s 的子串 s[i:j+1] 是回文串。显然我们有：
i > j,dp(i, j) = False, 空串不是回文串（dp数组是个上三角矩阵）j == j,dp(i, j) = True, 一个字符是回文串i < j, 这分为两种情况- 如果
s[i] == s[j], 那么dp(i, j) = dp(i+1, j-1) - 否则
dp(i, j) = False
- 如果
我们有了上述的初始值和递推式，如果我们能够先算出 dp(i+1, j-1)，就可以动规解这道题了。注意到 (i+1, j-1) 是 (i, j) 的左下位置。因此我们要从主对角线开始，依次向右上算。写出 DP 的代码如下。
class Solution_647:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
cnt = 0
for d in range(n): # d表示第几条斜对角线，d=0表示主对角线
for i in range(n - d):
j = i + d
# 这里有两种情况
# 1. i==j
# 2. i < j
# 所以用i+1 >= j-1判断是否有左下元素
if s[i] == s[j]:
dp[i][j] = 1 if i + 1 >= j - 1 else dp[i + 1][j - 1]
print(i, j)
if dp[i][j]:
cnt += 1
return cnt
同样可以使用 manacher 算法，对于一个回文串，它的回文子串的数目等于它长度的一半（每次去掉首位两个字符生成一个子串）。所以，我们使用 manacher 算法找出以每个字符为中心的回文子串的长度，然后对这些长度除于 2 （向下取整）再求和，就得到了字符串 s 的回文子串数目，幸运的是，manacher 求得的数组 p 正好是每个中心位置的回文子串的长度，所以我们直接 sum(v // 2 for v in p) 就可以了。manacher 的代码和上面一样，这里略去。
LeetCode 132. 给定一个字符串 s ，求把字符串 s 分割成全部都是回文子串的的最小分割次数。这个有一个前序题目LeetCode 131. 求出所有可能的划分。因为求出所有的划分必然要遍历所有的情况，所有我们直接用 DFS 就可以解了。同样我们可以延续这个思路，然后写出带 memo 的递归如下。
class Solution_132:
def minCut(self, s: str) -> int:
# 带 memo 的递归
memo = {}
def foo(idx):
nonlocal memo
if idx <= 0:
return 0
if idx in memo:
return memo[idx]
ans = len(s) # 最大的值是 len(s) - 1，我们在外面减 1，这里取len(s)
for i in range(idx - 1, -1, -1):
t = s[i:idx]
if t == t[::-1]:
ans = min(ans, 1 + foo(i))
memo[idx] = ans
return ans
return foo(len(s)) - 1
注意到上面的解法检查是否是回文串的时候用的是 t == t[::-1] 这没有用到回文串的性质。同时这个题目求最小的划分就是求尽可能长的回文子串（不一定是最长的划分次数最少，所以不能用贪心），上面说过，如果一个串 "aba" 是回文串，那么 "xabax" 也是回文串。因此我们可以用DP方法来检测一个子串是否是回文串，同时也把上述求最小划分次数的带 memo 递归过程转换成 DP 。
class Solution_132:
def minCut(self, s: str) -> int:
# 上面检查子串 t 是否回文的时候用的是暴力方法，我们可以利用
# 回文的性质，使用 DP 来检查一个子串是否是回文。
n = len(s)
dp = [[False] * (n+1) for _ in range(n+1)]
cut = [0] * n
for i in range(n):
cut[i] = i
for j in range(i+1):
# j + 1 > i - 1 means j is i-1 or i，in both case, s[j:i+1] is palindrome
if s[i] == s[j] and (j + 1 > i - 1 or dp[j+1][i-1]):
dp[j][i] = True
cut[i] = 0 if j == 0 else min(cut[i], cut[j-1]+1)
return cut[n-1]
当然，我们可以使用中心扩展法，这样可以省去 DP 检查是否回文部分的空间。
class Solution_132:
def minCut(self, s: str) -> int:
# 同样，我们也可以使用 中心扩展法，而不使用 DP 数组来记录子串是否是回文。
n = len(s)
cut = [i for i in range(-1, n)]
for idx in range(1, n):
for lo, hi in [(idx, idx), (idx - 1, idx)]: # 分别对应奇数长度和偶数长度的回文串两种情况
# 中心扩展
while lo >= 0 and hi < n and s[lo] == s[hi]:
# min(到 hi + 1 的划分次数， lo 位置划分次数 + 1)
cut[hi + 1] = min(cut[hi + 1], cut[lo] + 1)
lo -= 1
hi += 1
return cut[-1]
总结，回文是常常考到的一类题目，掌握常用的中心扩展法，和 DP 方法，能够解决不少回文串的相关的题目，然后本文重点讲的 manacher 算法，虽然在面试中环境下直接快速准确的写出这个算法不太容易，但对它的掌握依然十分必要~
多做题，多总结~