求调 附详细注释,代码不长
查看原帖
求调 附详细注释,代码不长
1509960
hjluojc楼主2025/7/28 16:17
#include <bits/stdc++.h>
using namespace std;

// Manacher算法实现:用于找到字符串中所有位置的最长回文半径
void manacher(const string &ss, vector<int> &p) {  
    // 预处理字符串,添加特殊字符统一处理奇偶长度回文
    string s = "$#";  // 开头添加特殊字符防止越界
    for (char c : ss) {
        s += c;      // 添加原字符
        s += '#';     // 每个字符后添加#
    }
    s += '^';        // 结尾添加特殊字符防止越界
    
    int n = s.size(); // 处理后的字符串长度
    p.resize(n, 0);   // 初始化回文半径数组
    
    int zh = 0;       // 当前最右回文的中心位置
    int right = 0;    // 当前最右回文的右边界
    
    for (int i = 1; i < n - 1; ++i) {
        // 利用对称性快速获取初始回文长度
        if (i < right) {
            p[i] = min(p[2 * zh - i], right - i);
        }
        // 中心扩展法尝试扩大回文半径
        while (s[i - p[i] - 1] == s[i + p[i] + 1]) {
            p[i]++;
        }
        // 更新最右回文信息
        if (i + p[i] > right) {
            zh = i;
            right = i + p[i];
        }
    }
}

int main() {
    string ss;
    cin >> ss;  // 输入原始字符串
    
    vector<int> p;  // 存储Manacher算法得到的回文半径
    manacher(ss, p); // 执行Manacher算法
    
    int n = ss.size();  // 原始字符串长度
    // left[i]表示以i结尾的最长回文长度
    // right[i]表示以i开始的最长回文长度
    vector<int> left(n + 2, 0), right(n + 2, 0);
    
    // 根据Manacher结果填充left和right数组
    for (int i = 1; i < (int)p.size(); ++i) {
        int l = i - p[i];  // 回文左边界(在处理后字符串中的位置)
        int r = i + p[i];   // 回文右边界(在处理后字符串中的位置)
        
        // 将回文信息映射回原始字符串
        // 计算原始字符串中的结束位置
        if (r <= n) {  
            left[r] = max(left[r], r - l);
        }
        // 计算原始字符串中的起始位置
        if (l >= 1) {  
            right[l] = max(right[l], r - l);
        }
    }

    // 预处理left数组:确保left[i]记录的是到i位置为止的最大回文长度
    for (int i = 1; i <= n; ++i) {
        left[i] = max(left[i], left[i - 1] - 1);
    }

    // 预处理right数组:确保right[i]记录的是从i位置开始的最大回文长度
    for (int i = n; i >= 1; --i) {
        right[i] = max(right[i], right[i + 1] - 1);
    }
    
    // 寻找两个不重叠回文的最大长度和
    int maxn = 0;
    for (int i = 1; i < n; ++i) {
        // 只有当左右都有回文时才计算
        if (left[i] && right[i + 1]) {
            maxn = max(maxn, left[i] + right[i + 1]);
        }
    }

    cout << maxn << endl;  // 输出结果
    return 0;
}
2025/7/28 16:17
加载中...