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

该算法的时间复杂度为 O(n²)。当字符串较长时，性能瓶颈明显。

Manacher 算法核心原理

Manacher 算法的关键在于利用已计算的信息加速后续计算。我们维护一个数组 d[i]，表示以 i 为中心的最长回文半径。同时，维护一个当前遍历到的最右回文边界 [l, r]。

关键性质

1. 回文半径数组：d[i] 记录以 i 为中心的回文半径。
2. 对称性：如果当前位置 i 在最右边界 r 之内，那么它关于中心 l + r - i 的对称点 j 的回文信息可以复用。
3. 边界更新：只有当新回文串的右端点超过 r 时，才更新 l 和 r。

分类讨论

当我们计算 d[i] 时，分两种主要情况：

1. i > r：当前点在已知最右回文串之外。此时没有历史信息可用，只能像中心扩展法一样暴力向外扩展，并更新 l 和 r。
2. i <= r：当前点在已知范围内。利用对称点 j = l + r - i 的信息：
   • 若 d[j] < r - i + 1：说明 j 的回文串完全在 [l, r] 内，由对称性可知 d[i] = d[j]。
   • 若 d[j] > r - i + 1：说明 j 的回文串超出了左边界 l，则 i 的回文串至少延伸到 r，即 d[i] = r - i + 1，之后需继续尝试扩展。
   • 若 d[j] == r - i + 1：边界刚好触及，同样需要尝试继续扩展。

这种策略保证了 r 指针在整个过程中只增不减，从而实现了 O(n) 的时间复杂度。

完整代码实现

下面是一个标准的 C++ 实现模板，可直接用于求解最长回文子串长度。

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

using namespace std;

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

// 预处理：添加分隔符
void init() {
    cin >> t;
    s = "#";
    for (char ch : t) {
        s += ch;
        s += '#';
    }
}

// Manacher 算法主逻辑
int manacher() {
    int n = s.size();
    int max_len = 0;
    int l = 0, r = -1; // 当前最右回文边界 [l, r]

    for (int i = 0; i < n; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);
        
        // 尝试扩展
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }
        
        d[i] = k;
        
        // 更新最右边界
        if (i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
        
        // 记录最大回文半径
        max_len = max(max_len, k - 1);
    }
    
    return max_len;
}

int main() {
    init();
    cout << manacher() << endl;
    return 0;
}

总结

Manacher 算法通过预处理消除奇偶差异，并利用回文串的对称性避免了大量重复比较。在实际工程中，如果你需要频繁查询或处理超长字符串的回文特征，这个算法是首选方案。记住，维护好 l 和 r 边界是理解该算法的关键所在。

对于更复杂的变体问题（如查找所有回文子串数量等），可以在上述基础上稍作修改。建议配合洛谷 P3805 等经典题目进行实战练习，加深理解。