查找字符串的最长子回文串
时间: 2023-05-17 18:04:46 浏览: 116
可以使用 Manacher 算法来查找字符串的最长子回文串。该算法的时间复杂度为 O(n),其中 n 是字符串的长度。以下是该算法的 Python 代码实现:
def find_longest_palindromic_substring(s):
# 预处理字符串,插入特殊字符
t = '#' + '#'.join(s) + '#'
n = len(t)
p = [0] * n # 记录每个位置的回文半径
center, right = 0, 0 # 记录当前最长回文串的中心和右边界
for i in range(1, n - 1):
if i < right:
p[i] = min(right - i, p[2 * center - i])
# 尝试扩展回文半径
while t[i + p[i] + 1] == t[i - p[i] - 1]:
p[i] += 1
# 更新最长回文串的中心和右边界
if i + p[i] > right:
center, right = i, i + p[i]
# 找到最长回文串的起始位置和长度
start, length = max(enumerate(p), key=lambda x: x[1])
return s[(start - length) // 2: (start + length) // 2]
对于字符串 "babad",该函数的返回值为 "bab" 或 "aba"。
阅读全文