1.求解最长回文子串
在之前博客中提到解决回文串问题时，是利用了大回文串 = 小回文串向两头扩展的性质得到状态转移方程，构建右上三角的dp table解决问题。
对于长度为n的字符串，用这种方式求解的时间复杂度是O(n^2)（需要填满右上三角的dp table）
另外，回文问题还有一种方法-中心扩展法：
在原字符串s中插入隔板，得到新字符串new_s，如s = 'abc'，new_s = '#a#b#c#'；遍历new_s 中的每一个元素ele，以ele为中心向两边扩展，得到关于ele对称的回文串。最坏时间复杂度O(n * n) = O(n^2)
2.马拉车算法（Manacher's Algorithm）
马拉车算法其实挺容易理解的
马拉车算法是对中心扩展法的改进，它的本质是利用已知的回文串的【对称性】减少重复计算，具体步骤如下：
- 1.插板。在原字符串s中插入隔板，得到新字符串new_s，如s = 'abc'，new_s = '#a#b#c#'。因为对于偶数长度的回文串，它关于''对称；而这种关于''对称的情况不如关于一个非空字符对称的奇数长度回文串好处理，干脆就先插板，把原来关于''对称的变成关于'#'对称的，可以统一在一个逻辑内处理
- 2.维护dp数组。dp[i]表示new_s[i]的回文半径，回文半径 = 回文中心 + 一侧长度，如abcba的回文半径是3
- 3.维护c_index和r_index两个变量。c_index表示已知的最靠右的回文串的中心位置，r_index表示已知的最靠右的回文串的右边界位置
- 4.**遍历new_s，从左到右填充dp，不断更新dp[i]、c_index和r_index **。具体过程如下：
如下图所示，假设当前红色方框内是已知的【最靠右】的回文子串，c_index 和 r_index 分别指向图示位置
-
情况 1：i > r_index
这时没什么好办法，从位置 i 中心扩散，得到以 new_s[i]为中心的最长回文串
-
情况 2：i <= r_index
如果i <= r_index，说明当前 check 的元素 new_s[i]位于一个已知的回文串内，那么其对称点易得为 new_s [c_index – (i-c_index)]
设 new_s[i]为中心的回文串为 H1，new_s [c_index – (i-c_index)]为中心的回文串为 H2
2.1 黄实框 H2 完全在红框内，即两框相离不存在交点时，
根据红框回文的对称性，H1 必然等于 H2，因此 dp[i] = dp[c_index-(i-c_index)]
2.2 黄实框 H2 越过红框，或者与红框边界重合，即两框存在交点时，
根据红框回文的对称性，只有下图左侧黄虚框内的字符串必然是 H1 的一部分， H2 越过红框的头和对应的尾都需要舍弃。这时只需要在左黄虚框对应的镜像— —【右黄虚框】的基础上做中心扩展就可以得到 H1，而不必总是从 new_s[i]开始 中心扩展。马拉车算法就省时在这里
例题
给定一个字符串 s，找到 s 中最长的回文子串的长度
马拉车算法代码如下：
class Solution:
def longestPalindrome(self, s: str) -> str:
# 马拉车算法
# 1.构建新字符串，统一为奇数长度
new_s = '#'
for ele in s:
new_s += ele + '#'
# 2.创建dp，dp[i]记录以new_s[i]为中心的回文串的回文半径
# 其中，回文半径 = 回文中心 + 一侧长度
l = len(new_s)
dp = [0 for i in range(l)]
# 3.维护两个变量 - 当前已知的最靠右的回文串中心c和右端r，初始化为-1
c = r = -1
for i in range(l):
if i > r:
# 常规暴力求解
temp = 1
for offset in range(1, l-i):
if new_s[i+offset] == new_s[i-offset]:
temp += 1
else:
break
dp[i] = temp
# 更新c和r
if i + temp - 1 > r:
r = i + temp - 1
c = i
else:
i2r_asRadius = r - i + 1
# dp[i]的对称点是dp[c-(i-c)]
if dp[c-(i-c)] < i2r_asRadius:
dp[i] = dp[c-(i-c)]
else:
temp = i2r_asRadius
for offset in range(i2r_asRadius, l-i):
if new_s[i+offset] == new_s[i-offset]:
temp += 1
else:
break
dp[i] = temp
# 更新c和r
if i + temp - 1 > r:
r = i + temp - 1
c = i
return max(dp)-1
虽然代码略长，但懂了原理还是很好写的
