题目描述
给定一个字符串，请你求出其中的最长回文子串的长度。

例如，给定字符串 Is PAT&TAP symmetric?，最长回文子串为 s PAT&TAP s，其长度是 11
11
。

输入格式
包含一个非空字符串。

输出格式
输出一个整数，表示给定字符串的最长回文子串的长度。

数据范围
给定字符串的长度不超过 1000
1000
。

输入样例：
Is PAT&TAP symmetric?
输出样例：
11

题解1：

#include<iostream>
#include<algorithm>
using namespace std;

// 中心扩展法：找到以 left 和 right 为中心的最长回文子串的长度
int expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1; // 返回回文子串的长度
}

int main() {
    string str;
    getline(cin, str); // 读取输入字符串
    int res = 0;

    for (int i = 0; i < str.size(); i++) {
        // 奇数长度的回文子串
        int len1 = expandAroundCenter(str, i, i);
        // 偶数长度的回文子串
        int len2 = expandAroundCenter(str, i, i + 1);
        // 更新最大值
        res = max(res, max(len1, len2));
    }

    cout << res << endl;
    return 0;
}

题解2：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

// 马拉车算法
int manacher(const string& s) {
    // 预处理字符串
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }

    int n = t.size();
    vector<int> p(n, 0); // p[i] 表示以 t[i] 为中心的最长回文半径
    int center = 0, right = 0; // 当前最右回文子串的中心和右边界
    int maxLen = 0; // 最长回文子串的长度

    for (int i = 0; i < n; i++) {
        // 利用对称性初始化 p[i]
        if (i < right) {
            p[i] = min(right - i, p[2 * center - i]);
        }

        // 中心扩展
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1]) {
            p[i]++;
        }

        // 更新最右回文子串
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }

        // 更新最长回文子串的长度
        maxLen = max(maxLen, p[i]);
    }

    return maxLen;
}

int main() {
    string str;
    getline(cin, str); // 读取输入字符串
    int res = manacher(str);
    cout << res << endl;
    return 0;
}