8.最长回文子串 python

### Python 实现最长回文子串算法 #### 方法一：暴力搜索法 暴力搜索法通过遍历所有可能的子串并检查其是否为回文来解决问题。这种方法简单直观，但时间复杂度较高。 ```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] ``` 此方法的时间复杂度为 O(n³)[^1]。 #### 方法二：动态规划法 动态规划法利用了回文的特点——如果一个字符串是回文，则去掉两端字符后的部分仍然是回文。这使得可以通过构建二维表的方式优化查找过程。 ```python def longestPalindrome_dp(s): n = len(s) dp = [[False] * n for _ in range(n)] start = 0 maxLength = 1 for i in range(n): dp[i][i] = True for cl in range(2, n + 1): for i in range(n - cl + 1): j = i + cl - 1 if s[i] == s[j] and cl == 2: dp[i][j] = True elif s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] and cl > maxLength: start = i maxLength = cl return s[start:start + maxLength] ``` 该方法的时间复杂度为 O(n²)[^2]。 #### 方法三：中心扩展法 中心扩展法则基于这样一个事实：任何长度大于等于3的回文都至少有一个中心位置。可以从每个潜在的中心向两侧扩散直到遇到不匹配为止。 ```python def expand_around_center(s, left, right): L, R = left, right while L >= 0 and R < len(s) and s[L] == s[R]: L -= 1 R += 1 return R - L - 1 def longestPalindrome_expand(s): if not s or len(s) < 1: return "" start = end = 0 for i in range(len(s)): len1 = expand_around_center(s, i, i) len2 = expand_around_center(s, i, i + 1) maxLen = max(len1, len2) if maxLen > end - start: start = i - (maxLen - 1) // 2 end = i + maxLen // 2 return s[start:end + 1] ``` 此方法同样具有较好的性能表现，在实际应用中往往能取得接近线性级别的效率[^4]。 #### 方法四：Manacher算法 Manacher算法是一种专门针对这个问题设计的有效解决方案，能够在O(n)时间内完成计算。它通过对原始字符串预处理以及巧妙地维护辅助数组实现了这一目标。 ```python def preprocess_string(s): if not s: return "^$" result = ["^"] for char in s: result.append("#") result.append(char) result.append("#$") return ''.join(result) def manachers_algorithm(s): T = preprocess_string(s) P = [0] * len(T) C = R = 0 for i in range(1, len(T)-1): mirr = 2*C - i if R > i: P[i] = min(R-i, P[mirr]) while T[i+(P[i]+1)] == T[i-(P[i]+1)]: P[i] += 1 if i + P[i] > R: C = i R = i + P[i] maxLen = 0 centerIndex = 0 for i in range(1, len(P)-1): if P[i] > maxLen: maxLen = P[i] centerIndex = i startIndex = (centerIndex - maxLen) // 2 return s[startIndex:startIndex + maxLen] ``` 上述四种方法各有优劣之处，具体选择取决于应用场景和个人偏好。其中Manacher算法由于其优秀的时空特性而被广泛推荐用于解决此类问题[^3]。