使用 Manacher 算法在 O(n) 时间内处理回文子串

1. 概述

在字符串处理中，我们经常会遇到“回文”这一概念。回文是指正着读和反着读都一样的字符串。例如："aba"、"aa"、"a" 是回文，而 "ab"、"abc" 不是。

在本教程中，我们将讲解 Manacher 算法，它能高效地找出字符串中所有以每个位置为中心的最长回文子串（包括奇数长度和偶数长度的回文），并且时间复杂度为 **O(n)**。

我们还会介绍 Manacher 算法的几个实际应用场景。

---

2. 基本概念

2.1 回文的定义

回文字符串是指从前往后和从后往前读都相同的字符串。例如：

✅ 回文示例："aba", "aa", "a", "abcacba"
❌ 非回文示例："ab", "cbabd"

回文的中心可以是一个字符（奇数长度）或两个字符之间的位置（偶数长度），中心两侧互为镜像。

2.2 问题定义

给定一个字符串 s，我们需要计算两个数组：

• oddP[i]：表示以 i 为中心的最长奇数长度回文子串的半径（不包括中心）
• evenP[i]：表示以 i 和 i+1 之间的位置为中心的最长偶数长度回文子串的半径

举个例子：

• s[i - oddP[i], i + oddP[i]] 是以 i 为中心的最长奇数长度回文
• s[i - evenP[i] + 1, i + evenP[i]] 是以 i 和 i+1 之间为中心的最长偶数长度回文

---

3. 暴力解法（Naive Approach）

暴力解法的思路是：对每个字符，向左右扩展，直到不能形成回文为止。

✅ 示例代码

public static int[] naiveLongestPalindromeSubstrings(String s) {
    int n = s.length();
    int[] oddP = new int[n];
    int[] evenP = new int[n];

    for (int i = 0; i < n; i++) {
        // 奇数长度回文
        int l = i, r = i;
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
            oddP[i] = (r - l) / 2;
            l--;
            r++;
        }

        // 偶数长度回文
        l = i;
        r = i + 1;
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
            evenP[i] = (r - l) / 2;
            l--;
            r++;
        }
    }

    return new int[]{oddP, evenP};
}

⚠️ 踩坑提醒

暴力解法的时间复杂度为 **O(n²)**，对于长度超过 10⁴ 的字符串会超时，因此需要更高效的算法。

---

4. Manacher 算法详解

Manacher 算法的核心思想是利用已知的回文信息，避免重复比较，从而将时间复杂度优化到 **O(n)**。

4.1 基本思想

我们维护一个当前最远的回文子串范围 [L, R]，其中心为 C。当我们处理到一个新的位置 i 时：

• 如果 i 在 [L, R] 范围内，我们可以利用对称性，直接从 mirror(i) 的结果中获取初始值
• 否则，我们从 0 开始扩展

4.2 奇数长度回文实现

public static int[] manacherOdd(String s) {
    int n = s.length();
    int[] oddP = new int[n];
    int C = 0, R = 0;

    for (int i = 0; i < n; i++) {
        int mirror = 2 * C - i;
        if (i < R) {
            oddP[i] = Math.min(R - i, oddP[mirror]);
        }

        // 尝试扩展
        int a = i + (1 + oddP[i]);
        int b = i - (1 + oddP[i]);
        while (a < n && b >= 0 && s.charAt(a) == s.charAt(b)) {
            oddP[i]++;
            a++;
            b--;
        }

        // 更新中心和右边界
        if (i + oddP[i] > R) {
            C = i;
            R = i + oddP[i];
        }
    }

    return oddP;
}

4.3 偶数长度回文实现

public static int[] manacherEven(String s) {
    int n = s.length();
    int[] evenP = new int[n];
    int C = 0, R = 0;

    for (int i = 0; i < n; i++) {
        int mirror = 2 * C - i - 1;
        if (i < R) {
            evenP[i] = Math.min(R - i, evenP[mirror]);
        }

        // 尝试扩展
        int a = i + evenP[i];
        int b = i - evenP[i] - 1;
        while (a < n && b >= 0 && s.charAt(a) == s.charAt(b)) {
            evenP[i]++;
            a++;
            b--;
        }

        // 更新中心和右边界
        if (i + evenP[i] > R) {
            C = i;
            R = i + evenP[i];
        }
    }

    return evenP;
}

4.4 正确性证明

我们始终维护最远的回文范围 [L, R]，这样可以确保每次扩展尽可能少地进行比较。

4.5 时间复杂度分析

• 每个字符最多被扩展一次
• 每次扩展都会导致右边界 R 右移
• 总共最多扩展 n 次

✅ 时间复杂度：O(n)

---

5. 应用场景

5.1 最长回文子串

使用 Manacher 算法后，只需遍历 oddP 和 evenP 数组，找出最大值即可。

int maxLen = 0;
for (int i = 0; i < n; i++) {
    maxLen = Math.max(maxLen, oddP[i] * 2 + 1);
    maxLen = Math.max(maxLen, evenP[i] * 2);
}

✅ 时间复杂度：O(n)

---

5.2 回文子串总数

int count = 0;
for (int i = 0; i < n; i++) {
    count += oddP[i] + 1;  // 单个字符也算
    count += evenP[i];
}

✅ 时间复杂度：O(n)

---

5.3 不同回文子串数量

为了统计不同子串，可以使用 Rabin-Karp 哈希算法 + HashSet：

Set<Long> hashes = new HashSet<>();
for (int i = 0; i < n; i++) {
    // 奇数长度
    for (int j = 1; j <= oddP[i]; j++) {
        long hash = hashFunction(s.substring(i - j, i + j + 1));
        hashes.add(hash);
    }
    // 偶数长度
    for (int j = 1; j <= evenP[i]; j++) {
        long hash = hashFunction(s.substring(i - j + 1, i + j + 1));
        hashes.add(hash);
    }
}

✅ 时间复杂度：O(n)
⚠️ 注意：哈希冲突需要处理，但通常可以忽略

---

6. 总结

功能	时间复杂度	说明
最长回文子串	O(n)	直接取 oddP 和 evenP 中最大值
回文子串数量	O(n)	对 oddP[i] + 1 和 evenP[i] 求和
不同回文子串数量	O(n)	使用哈希去重

Manacher 算法以其线性时间复杂度成为处理回文子串问题的利器，广泛应用于字符串匹配、文本处理等领域。

---

✅ 建议：掌握 Manacher 算法的原理和实现细节，有助于解决 LeetCode、Codeforces 等平台上的字符串难题。