题意概括

给定一个仅由数字和英文字母（大小写）组成的字符串 s，要求找出其最长的一个回文子串并输出。

数据范围:

• $1 \le s.length \le 1000$

基础知识

本题的核心是求解最长回文子串。解决这个问题有多种方法，其中最直观且效率足够应对本题数据范围的是 中心扩展法 (Expand Around Center)。

一个回文串是关于其中心对称的。中心可能是一个字符（对于奇数长度的回文串，如 "aba" 的中心是 "b"），也可能是两个字符之间的空隙（对于偶数长度的回文串，如 "abba" 的中心在两个 "b" 之间）。

对于一个长度为 $N$ 的字符串，它有 $N$ 个单字符中心和 $N-1$ 个字符间隙中心，总共有 $2N-1$ 个潜在的中心。

中心扩展法的思想是：

1. 遍历这 $2N-1$ 个潜在的中心。
2. 对于每一个中心，向两边同时扩展，判断左右两边的字符是否相等。
3. 如果相等，则继续扩展；如果不等，则停止扩展。此时就找到了以该点为中心的最长回文串。
4. 在所有中心扩展得到的回文串中，记录下最长的那一个作为最终答案。

例如，对于字符串 s = "babad":

• 以 a (索引 1) 为中心扩展，得到 bab。
• 以 a 和 b (索引 1 和 2) 之间的间隙为中心扩展，得到 ab (不是回文)。
• ... 遍历所有中心 ...
• 最终发现 bab 或 aba 是最长的。

该算法的时间复杂度为 $O(N^2)$，因为有 $O(N)$ 个中心，每个中心最多扩展 $O(N)$ 次。空间复杂度为 $O(1)$。对于 $N \le 1000$ 的数据范围，这个复杂度是完全可以接受的。

C++ 题解代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 全局变量存储输入字符串
string s;
// st: 最长回文子串的起始位置, len: 最长回文子串的长度
int st = 0, len = 0;

// 中心扩展函数
// 从 l 和 r 开始向两边扩展，寻找回文串
void f(int l, int r) {
    while (l >= 0 && r < s.size() && s[l] == s[r]) {
        l--;
        r++;
    }

    // 循环结束后, [l+1, r-1] 是以初始 l,r 为中心的最长回文串
    // 其长度为 (r-1) - (l+1) + 1 = r - l - 1
    if (r - l - 1 > len) {
        st = l + 1;
        len = r - l - 1;
    }
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> s;
    int n = s.size();

    // 如果字符串长度小于2，它本身就是最长回文子串
    if (n < 2) {
        cout << s << endl;
        return 0;
    }
    
    // 至少单个字符是回文的
    len = 1;

    // 遍历所有可能的中心点
    for (int i = 0; i < n; i++) {
        f(i, i);     // 以 s[i] 为中心的奇数长度回文串
        f(i, i + 1); // 以 s[i] 和 s[i+1] 之间为中心的偶数长度回文串
    }

    // substr(起始位置, 长度)
    cout << s.substr(st, len) << endl;

    return 0;
}