### Python 实现最长回文字符串算法 寻找最长回文子串是一个经典的动态规划问题，同时也存在多种高效解法。以下是几种常用的方法及其具体实现。 --- #### 方法一：动态规划 (Dynamic Programming) 动态规划的核心思想是通过构建一张二维布尔表 `dp[i][j]` 表示子串 `s[i:j+1]` 是否为回文。初始条件设置为所有单字符均为回文，并逐步扩展至更长的子串。 ```python def longest_palindrome_dp(s): n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] # 初始化 DP 表 start, max_len = 0, 1 # 记录最长回文子串的起始位置和长度 # 单个字符一定是回文 for i in range(n): dp[i][i] = True # 遍历不同长度的子串 for length in range(2, n + 1): # 子串长度从2开始 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 dp[i][j] and length > max_len: max_len = length start = i return s[start:start + max_len] # 示例测试 input_string = "babad" print(longest_palindrome_dp(input_string)) # 输出可能为 "bab" 或 "aba" ``` 这种方法的时间复杂度为 \(O(n^2)\)，空间复杂度也为 \(O(n^2)\)[^2]。 --- #### 方法二：中心扩展法 (Expand Around Center) 该方法基于这样一个事实：任何回文都可以看作是以某个中心向外扩展而成的。中心可以是一个单独的字符（奇数长度），也可以是在两个相邻字符之间（偶数长度）。遍历每个可能的中心并尝试扩展即可找到最长回文子串。 ```python def expand_around_center(s, left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left + 1:right] def longest_palindrome_expand(s): if not s: return "" res = "" for i in range(len(s)): # 奇数长度回文 odd = expand_around_center(s, i, i) if len(odd) > len(res): res = odd # 偶数长度回文 even = expand_around_center(s, i, i + 1) if len(even) > len(res): res = even return res # 示例测试 input_string = "cbbd" print(longest_palindrome_expand(input_string)) # 输出 "bb" ``` 此方法时间复杂度同样为 \(O(n^2)\)，但由于不需要额外的空间存储状态，因此空间复杂度仅为 \(O(1)\)[^3]。 --- #### 方法三：Manacher 算法 Manacher 算法是一种线性时间复杂度 (\(O(n)\)) 的最优解法，适用于求解最长回文子串问题。它通过对原字符串预处理使其仅包含奇数长度的回文，并维护一个辅助数组记录每个位置的最大回文半径。 ```python def preprocess(s): """ 对字符串进行预处理 """ if not s: return "^$" result = ["^"] for char in s: result.append("#") result.append(char) result.append("#$") return "".join(result) def manacher_algorithm(s): processed_s = preprocess(s) n = len(processed_s) P = [0] * n # 辅助数组，P[i]表示以第i个字符为中心的回文半径 C, R = 0, 0 # 当前中心C和右边界的R for i in range(1, n - 1): mirror_i = 2 * C - i # 关于当前中心C对称的位置 if R > i: P[i] = min(R - i, P[mirror_i]) # 尝试继续扩展边界 while processed_s[i + 1 + P[i]] == processed_s[i - 1 - P[i]]: P[i] += 1 # 更新中心和右边界 if i + P[i] > R: C, R = i, i + P[i] # 寻找最大回文半径对应的原始字符串 max_len, center_index = 0, 0 for i in range(1, n - 1): if P[i] > max_len: max_len = P[i] center_index = i start = (center_index - max_len) // 2 return s[start:start + max_len] # 示例测试 input_string = "abacdfgdcaba" print(manacher_algorithm(input_string)) # 输出 "aba" ``` Manacher 算法的关键在于充分利用已经计算过的信息减少不必要的比较次数[^4]。 --- ### 性能对比 | **方法** | **时间复杂度** | **空间复杂度** | |------------------|---------------|----------------| | 动态规划 | \(O(n^2)\) | \(O(n^2)\) | | 中心扩展法 | \(O(n^2)\) | \(O(1)\) | | Manacher 算法 | \(O(n)\) | \(O(n)\) | 尽管动态规划和中心扩展法易于理解和实现，但在性能要求较高的场合下，Manacher 算法则更为优越。 ---