Manacher 算法详解：线性时间求解最长回文子串

由于 r 在整个过程中只增不减，总比较次数是线性的。

代码实现

以下是完整的 C++ 实现，包含预处理、半径数组计算及结果提取。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

const int N = 2200005; // 根据题目数据范围调整
string t, s;
int d[N];

// 初始化与预处理
void init(const string& str) {
    s = "#";
    for (char ch : str) {
        s += ch;
        s += '#';
    }
}

// 计算回文半径数组
void get_d() {
    int len = s.length();
    int l = 0, r = -1; // 当前最右回文区间 [l, r]
    
    for (int i = 0; i < len; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);
        // 尝试扩展
        while (i - k >= 0 && i + k < len && s[i - k] == s[i + k]) {
            k++;
        }
        d[i] = k;
        // 更新最右区间
        if (i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
    }
}

int main() {
    cin >> t;
    init(t);
    get_d();
    
    int max_len = 0;
    for (int i = 0; i < s.length(); i++) {
        // 原始字符串长度 = 回文半径 - 1
        max_len = max(max_len, d[i] - 1);
    }
    cout << max_len << endl;
    return 0;
}

总结

Manacher 算法通过预处理统一奇偶回文，并利用对称性和最右边界记录，成功将最长回文子串问题的复杂度从 O(n²) 降低到 O(n)。掌握该算法的关键在于理解 d[i] 的推导过程以及 l, r 区间的维护逻辑。在实际竞赛或工程场景中，遇到大规模字符串回文匹配问题时，这是首选方案。