L2-008 最长对称子串Python

### L2-008 最长对称子串 Python 实现方法 以下是基于Python实现的解决L2-008最长对称子串问题的方法。此算法通过遍历字符串中的每一个字符作为中心点，分别向两侧扩展来检测可能存在的回文子串。 #### 中心扩展法 这种方法的核心思想是以每个字符为中心，尝试向外扩展以找到最大的回文子串长度。对于奇数长度和偶数长度的回文子串都需要考虑[^3]。 ```python def longest_palindrome_length(s): res = 0 length = len(s) # 遍历每个位置作为中心点 for i in range(length): # 奇数长度回文子串 j = 0 while i - j >= 0 and i + j < length and s[i - j] == s[i + j]: j += 1 res = max(res, 2 * (j - 1) + 1) # 偶数长度回文子串 j = 0 while i - j >= 0 and i + j + 1 < length and s[i - j] == s[i + j + 1]: j += 1 res = max(res, 2 * j) return res if __name__ == "__main__": str_input = input() result = longest_palindrome_length(str_input) print(result) ``` 这段代码实现了两种情况下的回文查找：一种是从单个字符出发的奇数长度回文；另一种是从两个相邻字符之间的间隙出发的偶数长度回文[^3]。 #### 动态规划法（备选） 虽然题目提到可以通过暴力解法完成，但如果希望优化时间复杂度，可以采用动态规划的方式解决问题。定义`dp[i][j]`表示从索引`i`到`j`的子串是否为回文，则状态转移方程如下： - 如果`s[i] == s[j]`且`(j - i <= 2)`或者`dp[i+1][j-1] == True`，则`dp[i][j] = True`。 最终的结果即为满足条件的最大`j - i + 1`[^4]。 ```python def longest_palindrome_dp(s): n = len(s) if n == 0: return 0 dp = [[False]*n for _ in range(n)] max_len = 1 # 初始化单个字符的情况 for i in range(n): dp[i][i] = True # 构建DP表 for j in range(1, n): for i in range(j): if s[i] == s[j] and ((j - i <= 2) or dp[i+1][j-1]): dp[i][j] = True current_len = j - i + 1 if current_len > max_len: max_len = current_len return max_len if __name__ == "__main__": str_input = input() result = longest_palindrome_dp(str_input) print(result) ``` 以上两段代码均能有效求解最长对称子串问题，并可根据实际需求选用不同的实现方式。