回文子串是正反读相同的连续子串，常用中心扩展法在O(n²)时间内找出最长回文子串；也可通过动态规划或Manacher算法优化处理。
判断和找回文子串是字符串处理中的常见问题。回文子串指的是正着读和反着读都一样的连续子串，比如 "aba" 或 "abba"。在 Python 中有几种有效的方法可以找出一个字符串中所有的回文子串，或者最长的回文子串。
1. 中心扩展法
回文串的特征是以某个位置或两个位置之间的空隙为中心，向两边对称扩展。我们可以枚举每个可能的中心点，然后向左右扩展，判断是否构成回文。
这种方法的时间复杂度为 O(n²)，空间复杂度为 O(1)，适合找最长回文子串。
立即学习“Python免费学习笔记（深入）”；
def longest_palindrome(s):
if not s:
return ""
<pre class='brush:python;toolbar:false;'>start = 0
max_len = 1
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# 返回长度（注意边界）
return right - left - 1
for i in range(len(s)):
len1 = expand_around_center(i, i) # 奇数长度回文
len2 = expand_around_center(i, i+1) # 偶数长度回文
current_max = max(len1, len2)
if current_max > max_len:
max_len = current_max
start = i - (current_max - 1) // 2
return s[start:start + max_len]调用示例：
print(longest_palindrome("babad")) # 输出："bab" 或 "aba"
print(longest_palindrome("cbbd")) # 输出："bb"
2. 找出所有回文子串
如果目标是找出字符串中所有的回文子串，可以在中心扩展的基础上稍作修改，收集每一个找到的回文串。
立即学习“Python免费学习笔记（深入）”；
def find_all_palindromes(s):
palindromes = set() # 使用集合避免重复
<pre class='brush:python;toolbar:false;'>def expand_and_add(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
palindromes.add(s[left:right+1])
left -= 1
right += 1
for i in range(len(s)):
expand_and_add(i, i) # 奇数长度
expand_and_add(i, i+1) # 偶数长度
return list(palindromes)示例：
print(find_all_palindromes("aabbaa"))
# 输出可能包含："a", "b", "aa", "bb", "abba", "aabbaa" 等
3. 动态规划方法
也可以使用动态规划来解决最长回文子串问题。定义 dp[i][j] 表示从索引 i 到 j 的子串是否为回文。
状态转移方程：
- 如果 s[i] == s[j]，且内部子串 dp[i+1][j-1] 是回文，或者子串长度 ≤ 2，则 dp[i][j] = True
时间复杂度 O(n²)，空间复杂度 O(n²)。
立即学习“Python免费学习笔记（深入）”；
def longest_palindrome_dp(s):
n = len(s)
if n == 0:
return ""
<pre class='brush:python;toolbar:false;'>dp = [[False] * n for _ in range(n)]
start = 0
max_len = 1
# 单个字符都是回文
for i in range(n):
dp[i][i] = True
# 检查长度为2的子串
for i in range(n - 1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start = i
max_len = 2
# 检查长度大于2的子串
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
start = i
max_len = length
return s[start:start + max_len]4. 使用 Manacher 算法（进阶）
Manacher 算法可以在 O(n) 时间内找出最长回文子串，适合处理大规模数据。实现较为复杂，一般面试中了解即可。
其核心思想是利用回文的对称性，避免重复计算。
基本上就这些常用方法。中心扩展法最直观、易理解，推荐日常使用。动态规划逻辑清晰但耗空间，而 Manacher 是性能最优解。根据实际需求选择合适的方法即可。
