编写函数,参数为一个字符串,返回这个字符串所有子串里面构成回文串的最大子串。
时间: 2024-10-21 08:06:49 浏览: 53
C语言求两个字符串的最长公共子串
5星 · 资源好评率100%
编写这样的函数通常涉及动态规划或中心扩散算法,目的是找到给定字符串中最长的回文子串。这里是一个简单的Python示例:
```python
def longest_palindrome_substring(s):
if not s:
return ""
# 初始化最长回文子串长度为0,以及两个指针
max_len = 0
start = 0
# 遍历字符串,对于每个字符作为中心点,向两边扩张
for i in range(len(s)):
# 检查以当前字符为中心的奇数长度回文
len1 = expand_around_center(s, i, i)
# 检查以当前字符和下一个字符组成的偶数长度回文
len2 = expand_around_center(s, i, i + 1)
# 取两者中的最大值作为新的回文长度
max_len = max(max_len, len1, len2)
# 如果新长度大于原来的最长回文长度,更新起始位置
if max_len > i - start:
start = i - max_len + 1
# 返回最长回文子串
return s[start:start+max_len]
# 辅助函数,用于检查并延伸以特定字符为中心的回文序列
def expand_around_center(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
# 示例:
s = "babad"
print(longest_palindrome_substring(s)) # 输出:"bab" 或 "aba"
```
阅读全文