C++怎么实现Manacher算法_C++在线性时间内查找最长回文子串

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

string longestPalindrome(string s) {
    if (s.empty()) return "";

    // 预处理字符串
    string transformed = "^#";
    for (char c : s) {
        transformed += c;
        transformed += '#';
    }
    transformed += '$';

    int n = transformed.size();
    vector<int> P(n, 0);
    int center = 0, right = 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 (transformed[i + P[i] + 1] == transformed[i - P[i] - 1]) {
            P[i]++;
        }

        // 更新中心和右边界
        if (i + P[i] > right) {
            center = i;
            right = i + P[i];
        }
    }

    // 找最长回文
    int maxLen = 0, maxCenter = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            maxCenter = i;
        }
    }

    int start = (maxCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

// 测试
int main() {
    string s = "babad";
    cout << longestPalindrome(s) << endl; // 输出 bab 或 aba
    return 0;
}