5. 最长回文子串

题目

5. 最长回文子串（中等）

在线练习：https://www.nowcoder.com/share/jump/5832603751775720167173

给你一个字符串 s，找到 s 中最长的回文子串。

• 回文串指正读和反读都相同的字符串
• 子串为原字符串中连续的一段字符

示例 1：

输入：

cdabbacc

输出：

4

解释：最长回文子串为 “abba”

示例 2：

输入：

abbacde

输出：

4

解释：最长回文子串为 “abba”

思路

中心扩展法：回文串具有中心对称的特性，从中心向两端扩展，直到不再是回文串。回文串的中心可以是单个字符（奇数长度）或两个相邻字符（偶数长度）。

关键点：

• 奇数长度回文（如 “aba”）：中心是单个字符
• 偶数长度回文（如 “abba”）：中心是两个字符之间

枚举每个可能的中心点，向两边扩展，每个位置需要扩展两次：

1. expand(i, i) - 以 i 为中心（奇数长度）
2. expand(i, i+1) - 以 i 和 i+1 之间为中心（偶数长度）

比较更新最长回文子串的起止位置。

进阶：区间 DP——f[i][j] 表示 s[i..j] 是否为回文，按子串长度转移，$O(n^2)$；Manacher 算法可优化到 $O(n)$。

代码

方法一：expand 函数版（输出长度）

s = input().strip()

res = ""

def expand(l, r):
    """从中心 (l, r) 向两边扩展，返回最长回文子串"""
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l + 1: r]

for i in range(len(s)):
    res = max(res, expand(i, i), key=len)     # 奇数长度回文
    res = max(res, expand(i, i + 1), key=len) # 偶数长度回文

print(len(res))

方法二：起止下标版（输出子串）

import sys

s = sys.stdin.readline().strip()

def fun(s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return l + 1, r - 1

start, end = 0, 0
for i in range(len(s)):
    l1, r1 = fun(s, i, i)
    l2, r2 = fun(s, i, i + 1)
    if r1 - l1 > end - start:
        start, end = l1, r1
    if r2 - l2 > end - start:
        start, end = l2, r2

print(s[start: end + 1])

代码解析

expand(l, r) 函数

初始:    l = i, r = i          l = i, r = i+1
         a b a                  a b b a
            ↑                      ↑ ↑
           中心                  中心

扩展:   l--, r++               l--, r++

• while l >= 0 and r < len(s)：边界检查
• s[l] == s[r]：回文判断，两边字符相等则继续扩展
• s[l + 1: r]：循环结束时 l 和 r 都越界了一步，需要修正

max(res, expand(i, i), key=len) 解析

部分	含义
max()	Python 内置函数，返回最大值
res	当前找到的最长结果
expand(i, i)	从中心 i 向两边扩展查找回文串
key=len	比较长度作为判断标准

选择 res 和 expand(i, i) 中长度更长的那个作为新的 res。

方法二要点：

• fun(s, l, r)：以 l, r 为中心扩展，返回回文串的起止位置
• 奇数中心 (i, i)：处理 “aba” 类型
• 偶数中心 (i, i+1)：处理 “abba” 类型

复杂度

• 时间复杂度 O(n²)：n 个中心点，每个中心点最多扩展 n 次
• 空间复杂度 O(1)：只使用常数额外空间（不含输入和输出）