Manacher 线性时间最长回文子串

📖 算法原理：镜像对称复制与右边界探索

最长回文子串问题是指在给定字符串 $S$ 中，寻找长度最长的回文子串。朴素算法以每个点为中心向外双向扩展，最坏时间复杂度为 $O(N^2)$。Manacher 算法利用已知回文的对称性，实现完美的 $O(N)$ 线性复杂度。

📐 核心步骤与镜像复制定理

预处理填充：在所有相邻字符之间及首尾插入特殊占位符 #（并在最左/右侧加哨兵 ^ / $），从而将所有奇数长度与偶数长度回文统一化为奇数长度回文。
核心变量定义：
- r[i]：以索引 $i$ 为回文中心向外扩展的回文半径（包括 $i$ 本身）。
- C：当前探索出的能触及最右侧的回文中心。
- R：中心 C 覆盖的右边界：R = C + r[C]。
镜像对称加速（最核心）：当计算 $i$ 处的半径 r[i] 时，若 $i < R$，设 $i$ 关于对称中心 $C$ 的对称镜像点为 $i' = 2 \cdot C - i$。根据回文对称性：
$r[i] = \min(R - i, r[i'])$
这意味着我们能瞬间复制 $i'$ 处的已知回文半径，直接跳过大量冗余的向外字符比较！
单向扩展与更新：在复制完初始半径后，若未出边界，则继续向外双向比对字符扩展半径，若更新后 $i + r[i] > R$，则将中心 $C$ 重新挂接到 $i$，更新 $R$。

输入原始串：

演示速度：

输入原始串并点击“开始线性匹配”或“单步计算”，观摹镜像对称半径复制及扩展流程。

🔎 Manacher 双指针镜像扫描器 (Symmetry Radius Copy Visualizer)

当前计算中心 i

对称镜像点 i'

最右覆盖中心 C

最右边界 R

void manacher(string s) {
    string t = init(s); // 插入占位符 ^#a#b#a#$
    int n = t.length();
    vector<int> r(n, 0);
    int c = 0, r_boundary = 0; // C 中心与 R 边界
    
    for (int i = 1; i < n - 1; i++) {
        int i_mirror = 2 * c - i; // 获取 i 对称的镜像点 i'
        
        if (i < r_boundary) {
            // 核心：直接对称复制镜像点的已知半径！
            r[i] = min(r_boundary - i, r[i_mirror]); 
        }
        
        // 双指针向两端暴力扩展
        while (t[i - r[i] - 1] == t[i + r[i] + 1]) {
            r[i]++; 
        }
        
        // 若超出当前最右边界，则重定位更新 C 和 R
        if (i + r[i] > r_boundary) {
            c = i;
            r_boundary = i + r[i];
        }
    }
}

📋 镜像对称探测计算历史