03-最长回文子串

题目描述

给定一个字符串S，请你求出S的最长回文子串。

输入描述

输入仅一行，包含一个字符串S。

1≤∣S∣≤5×1051≤∣S∣≤5×105，保证S只包含小写字母、大写字母、数字。

输出描述

输出共1行，包含一个整数，表示答案。

输入输出样例

输入

aa1ABA1b

输出

5

思路分析：

对于求字符串的最长回文子串，可以使用中心扩展法。

回文串分为奇数长度和偶数长度两种情况：

对于奇数长度的回文串，中心是一个字符；对于偶数长度的回文串，中心是两个字符。

从字符串的每个位置开始，分别向左右两边扩展，检查是否构成回文串，并记录最长的回文子串。

代码示例： 

s=input()
max_palindrome=""

# 中心扩展函数，用于检查以left和right为中心的回文子串aa11b b11aa
def expand(left, right):
    # 当left和right在字符串范围内且对应位置的字符相等时，继续扩展
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # 返回以left和right为中心的回文子串（不包括left和right超出范围的部分）
    return s[left + 1:right]
# 遍历字符串的每个位置
for i in range(len(s)):
    # 检查奇数长度的回文子串
    odd_palindrome = expand(i, i)
    # 如果当前奇数长度的回文子串比之前找到的最长回文子串长，则更新最长回文子串
    if len(odd_palindrome) > len(max_palindrome):
        max_palindrome = odd_palindrome
    # 检查偶数长度的回文子串（以i和i+1为中心）
    even_palindrome = expand(i, i + 1)
    # 如果当前偶数长度的回文子串比之前找到的最长回文子串长，则更新最长回文子串
    if len(even_palindrome) > len(max_palindrome):
        max_palindrome = even_palindrome

# 输出最长回文子串长度
print(len(max_palindrome))