题意分析

1. 问题目标：

   • 给定一个字符串，找到其中的最长回文子串的长度。
   • 回文子串是指正读和反读都相同的子串。

2. 关键点：

   • 字符串长度可能达到$1000000$，需要高效的算法。
   • 不能使用暴力方法（时间复杂度$O(n^3)$或$O(n^2)$），否则会超时。

3. 示例解释：

   • 第一个测试用例中，最长回文子串是"abcbabcbabcba"，长度为$13$。
   • 第二个测试用例中，最长回文子串是"baaaab"，长度为$6$。

解题思路

Manacher算法：

1. 预处理字符串：

   • 在每个字符之间插入特殊字符（如#），将字符串长度统一为奇数，简化处理。
   • 例如，字符串"abba"预处理后变为"#a#b#b#a#"。

2. 维护回文半径数组：

   • 定义数组p，其中p[i]表示以字符t[i]为中心的最长回文半径。
   • 初始化center和right，分别表示当前最右回文串的中心和右边界。

3. 扩展回文半径：

   • 对于每个位置i，利用对称性快速初始化p[i]。
   • 向左右扩展，直到字符不匹配，更新p[i]。
   • 如果当前回文串的右边界超过right，更新center和right。

4. 计算最长回文长度：

   • 遍历p数组，找到最大值即为最长回文子串的长度。

解决代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int manacher(const string &s) {
    string t = "#";
    for (size_t i = 0; i < s.size(); ++i) {
        t += s[i];
        t += '#';
    }
    int n = t.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    int max_len = 0;
    for (int i = 1; i < n - 1; ++i) {
        int mirror = 2 * center - i;
        if (i < right) {
            p[i] = min(right - i, p[mirror]);
        }
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && t[i + p[i] + 1] == t[i - p[i] - 1]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        max_len = max(max_len, p[i]);
    }
    return max_len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    int TC = 0;
    while (cin >> s) {
        if (s == "END") break;
        int ans = manacher(s);
        cout << "Case " << ++TC << ": " << ans << '\n';
    }
    return 0;
}