最长回文子串

马拉车算法（Manacher’s Algorithm）是用于高效查找字符串中最长回文子串的算法。其核心在于通过对称性和预处理，将寻找最长回文子串的时间复杂度优化到 O(n)。以下是详细原理和示例解析：

一、核心思想

1. 回文的性质
   回文中心对称，但存在两种类型：

• 奇数长度：如 "aba"，中心为单个字符 'b'。
• 偶数长度：如 "abba"，中心在两个字符 'b' 之间。

1. 预处理：统一奇偶长度
   为了统一处理，在原始字符串的每个字符间插入特殊字符（如 #），并在首尾添加不同字符（如 ^ 和 $）避免边界检查。
   示例：
   原始字符串 "babad" → 预处理后 "^#b#a#b#a#d#$"

• 奇数长度回文变为以 # 为中心，偶数长度回文变为以原字符为中心。

二、关键步骤

1. 定义数组 len[]

• len[i] 表示以预处理字符串中第 i 个字符为中心的最长回文半径（包含自身）。
• 实际回文长度 = len[i] - 1（例如，len[i]=4 对应长度为 3 的回文）。

1. 维护对称性

• 用 center 和 right 记录当前已知的最右回文子串的中心和右边界。
• 当处理位置 i 时，若 i 在 right 左侧，可利用对称点 mirror = 2*center - i 的信息快速初始化 len[i]。

1. 中心扩展

• 从 i 向两侧扩展，直到无法匹配，更新 len[i]。
• 若扩展后的右边界超过 right，则更新 center 和 right。

三、示例解析：以 "babad" 为例

1. 预处理字符串
   原始字符串：b a b a d
   预处理后：^ # b # a # b # a # d #$
   索引：0 1 2 3 4 5 6 7 8 9 10 11
2. 计算 len[] 数组
   遍历每个位置 i，利用对称性和扩展规则：

3. 结果提取

• 最大 len[i] 为 4（位置 i=4 和 i=6）。
• 最长回文子串长度 = 4 - 1 = 3。
• 起始位置：(i - len[i]) / 2 = (4-4)/2 = 0 → 原字符串的 "bab" 或 (6-4)/2=1 → "aba"。

四、算法优势

1. 线性时间复杂度：每个字符最多被访问两次（扩展和对称性利用）。
2. 统一处理奇偶长度：通过预处理简化逻辑。
3. 避免重复计算：利用对称性减少扩展次数。

五、关键代码逻辑（C++）

string longestPalindrome(string s) {
    string t = preprocess(s); // 预处理
    int n = t.size();
    vector<int> len(n, 0);
    int center = 0, right = 0;
    int max_len = 0, max_center = 0;

    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * center - i;

        // 利用对称性初始化 len[i]
        if (i < right)
            len[i] = min(right - i, len[mirror]);

        // 中心扩展
        while (t[i + len[i] + 1] == t[i - len[i] - 1])
            len[i]++;

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

        // 更新最大值
        if (len[i] > max_len) {
            max_len = len[i];
            max_center = i;
        }
    }

    // 转换为原字符串的起始位置
    int start = (max_center - max_len) / 2;
    return s.substr(start, max_len);
}

六、总结
马拉车算法通过预处理统一奇偶回文，并利用对称性优化计算，高效找到最长回文子串。其核心在于维护 len[] 数组和动态调整 center 与 right，确保每个字符仅被访问常数次，最终达到 O(n) 的时间复杂度。