### Python 实现最长回文子串算法 以下是几种常见的方法来实现寻找最长回文子串的 Python 程序： #### 方法一：暴力搜索法 这种方法通过遍历所有的可能子串，并逐一判断它们是否为回文。尽管其实现简单，但由于时间复杂度较高 \(O(n^3)\)，因此不适用于非常长的字符串。 ```python def longestPalindrome_brute_force(s): def is_palindrome(substring): return substring == substring[::-1] n = len(s) max_len = 0 start = 0 for i in range(n): for j in range(i, n): if is_palindrome(s[i:j+1]) and (j - i + 1) > max_len: max_len = j - i + 1 start = i return s[start:start + max_len] # 返回最长回文子串[^1] ``` --- #### 方法二：动态规划法 此方法利用二维布尔数组 `dp` 来存储子串的状态信息。如果子串 \(s[i..j]\) 是回文，则设置 `dp[i][j]=True`；否则设为 `False`。该方法的时间复杂度为 \(O(n^2)\)。 ```python def longest_palindrome_dp(s): n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] start, max_len = 0, 1 for i in range(n): dp[i][i] = True for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j]: if length == 2 or dp[i + 1][j - 1]: dp[i][j] = True if length > max_len: max_len = length start = i return s[start:start + max_len] # 更新最长回文长度和起始点[^2] ``` --- #### 方法三：中心扩展法 这种方法基于观察到的事实——任何回文都围绕某个中心展开。可以枚举每个可能的中心位置（单字符或双字符），并向两侧扩展直到不再满足回文条件为止。时间复杂度同样为 \(O(n^2)\)。 ```python class Solution_center_expansion(object): def expand_around_center(self, s, left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1 def longestPalindrome(self, s): start, end = 0, 0 for i in range(len(s)): l1, r1 = self.expand_around_center(s, i, i) # 奇数长度回文 l2, r2 = self.expand_around_center(s, i, i + 1) # 偶数长度回文 if r1 - l1 > end - start: start, end = l1, r1 if r2 - l2 > end - start: start, end = l2, r2 return s[start:end + 1] # 使用中心扩展法查找最长回文子串[^3] ``` --- #### 方法四：Manacher 算法 这是目前最优的方法之一，能够在线性时间内完成任务 (\(O(n)\))。它通过对原始字符串预处理，在新构建的字符串基础上执行特定逻辑操作从而快速定位最大回文半径。 由于 Manacher 的具体实现较为复杂，这里仅提供核心思路而不展示完整代码片段。 --- ### 总结 以上介绍了四种不同的解决方案用于求解最长回文子串问题，各有优劣之处。实际应用时可根据输入规模以及性能需求选择合适的策略。