每日算法 — 使用java实现最长回文子串：Manacher算法与中心扩展优化

引言：回文的魅力

“上海自来水来自海上”、”山山花山上开”——中文里有许多有趣的回文。在计算机科学中，回文串（Palindrome）指正读反读都相同的字符串。寻找字符串中的最长回文子串，是面试与算法竞赛中的经典问题。

朴素的中心扩展法时间复杂度为 O(n²)，而 1975 年 Glenn Manacher 提出的 Manacher 算法 利用回文的对称性，将时间复杂度优化到 O(n)，成为该问题的最优解。本文将用 Java 完整实现这一算法，并对比中心扩展法的思路演进。

问题定义

给定一个长度为 n 的字符串 s，找出其中最长的连续子串，使得该子串正读反读相同。

示例：
– 输入："babad" → 输出："bab" 或 "aba"
– 输入："cbbd" → 输出："bb"
– 输入："a" → 输出："a"

解法一：中心扩展法

核心思想

回文串的中心可能是一个字符（奇数长度，如 "aba"），也可能是两个字符之间（偶数长度，如 "abba"）。因此，共有 2n - 1 个可能的中心位置。

对每个中心，向两侧同步扩展，直到字符不再相等。

Java 实现

/**
 * 中心扩展法求解最长回文子串
 * 时间复杂度: O(n²)，空间复杂度: O(1)
 */
public class CenterExpand {

    /**
     * 以 left 和 right 为中心向两侧扩展，返回扩展后的回文边界
     * @param s 原字符串
     * @param left 左边界（初始时可能与 right 相同或相差1）
     * @param right 右边界
     * @return 回文子串的起止索引 [start, end]
     */
    private int[] expand(String s, int left, int right) {
        // 当两侧字符相等时继续扩展
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 循环退出时，left 和 right 已经多走了一步，需要回退
        return new int[]{left + 1, right - 1};
    }

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, end = 0;
        // 遍历每一个可能的中心位置（共 2n-1 个）
        for (int i = 0; i < s.length(); i++) {
            // 奇数长度回文：中心为单个字符 s[i]
            int[] odd = expand(s, i, i);
            // 偶数长度回文：中心为 s[i] 和 s[i+1] 之间
            int[] even = expand(s, i, i + 1);

            // 取较长的回文
            int[] longer = (odd[1] - odd[0] > even[1] - even[0]) ? odd : even;
            if (longer[1] - longer[0] > end - start) {
                start = longer[0];
                end = longer[1];
            }
        }
        return s.substring(start, end + 1);
    }

    public static void main(String[] args) {
        CenterExpand solution = new CenterExpand();
        String[] testCases = {"babad", "cbbd", "a", "ac", "racecar", "abacdfgdcaba"};
        for (String tc : testCases) {
            System.out.println("输入: " + tc + " -> 最长回文: " + solution.longestPalindrome(tc));
        }
    }
}

复杂度分析

• 时间复杂度：O(n²)。每个中心平均扩展 O(n) 次，共 2n-1 个中心。
• 空间复杂度：O(1)。仅使用常数额外空间。

中心扩展法思路直观、代码简洁，是面试中的标准答案。但当字符串极长（如 10⁶ 级别）时，O(n²) 的复杂度可能超时，这就需要 Manacher 算法。

解法二：Manacher 算法

关键洞察：对称性复用

Manacher 算法的核心思想是：利用已计算出的回文信息，避免重复扩展。

设想字符串 "abacaba"，当我们从左向右扫描时：
– 在位置 3（字符 'c'）发现以它为中心的回文半径为 3（覆盖 "abacaba"）。
– 在位置 4（字符 'a'），它关于中心 'c' 的对称点是位置 2（字符 'a'）。
– 位置 2 的回文半径已知，因此位置 4 的回文半径至少不会小于位置 2 的半径——除非被右边界限制。

这就是 对称性复用 的精髓。

预处理：统一奇偶

为了消除奇偶长度的区分，Manacher 算法在字符间插入一个分隔符（如 '#'），并在首尾添加哨兵：

• 原串："abba"
• 处理后："^#a#b#b#a#$"

这样，所有回文都变成了以某个 '#' 或实际字符为中心的奇数长度回文，统一了处理逻辑。

核心变量定义

递推规则

对每个位置 i，设 mirror = 2*C - i：

1. 若 i < R（在当前最右回文内部）：
2. P[i] 至少等于 min(P[mirror], R - i)
3. 如果 P[mirror] 较小，说明 mirror 的回文完全包含在 C 的回文内，由对称性，i 的回文半径就是 P[mirror]

4. 如果 R - i 较小，说明 i 的回文可能超出 R，需要从 R 开始继续扩展

5. 若 i >= R（超出当前最右回文）：

6. 无法利用对称性，P[i] 从 0 开始中心扩展

7. 尝试扩展：从当前估计的半径开始，继续向两侧扩展，更新 P[i]

8. 更新最右边界：如果 i + P[i] > R，则更新 C = i，R = i + P[i]

完整 Java 实现

import java.util.Arrays;

/**
 * Manacher 算法求解最长回文子串
 * 时间复杂度: O(n)，空间复杂度: O(n)
 */
public class ManacherAlgorithm {

    /**
     * 预处理字符串：在字符间插入 '#'，并在首尾添加哨兵 '^' 和 '$'
     * 例如 "abba" -> "^#a#b#b#a#$"
     * 哨兵确保扩展时不会越界，同时消除奇偶长度差异
     */
    private String preprocess(String s) {
        if (s == null || s.isEmpty()) return "^$";
        StringBuilder sb = new StringBuilder("^");
        for (int i = 0; i < s.length(); i++) {
            sb.append('#').append(s.charAt(i));
        }
        sb.append("#$");
        return sb.toString();
    }

    /**
     * Manacher 算法主逻辑
     * @param s 原字符串
     * @return 最长回文子串
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        String t = preprocess(s);
        int n = t.length();
        // P[i] 表示以 T[i] 为中心的回文半径（向单侧延伸的长度）
        int[] p = new int[n];
        // C: 当前最右回文的中心，R: 当前最右回文的右边界（右开）
        int center = 0, right = 0;

        // 记录最长回文的位置和半径
        int maxLen = 0, centerIndex = 0;

        // 遍历处理后的字符串，跳过哨兵 '^' 和 '$'
        for (int i = 1; i < n - 1; i++) {
            // mirror 是 i 关于 center 的对称点
            int mirror = 2 * center - i;

            // 核心优化：如果 i 在当前最右回文内部，利用对称性获得初始半径估计
            if (i < right) {
                // P[mirror] 是已知信息，但回文不能超过右边界 right
                p[i] = Math.min(right - i, p[mirror]);
            }

            // 尝试从当前估计半径向外扩展
            // 由于哨兵 '^' 和 '$' 的存在，无需检查越界
            while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
                p[i]++;
            }

            // 如果扩展后的回文超出了当前最右边界，更新 center 和 right
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }

            // 记录最长回文
            if (p[i] > maxLen) {
                maxLen = p[i];
                centerIndex = i;
            }
        }

        // 将处理串中的索引映射回原串索引
        // centerIndex 是处理串中的中心，maxLen 是半径
        // 原串起始位置 = (centerIndex - maxLen) / 2
        int start = (centerIndex - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }

    /**
     * 扩展版：返回所有回文子串的半径数组，便于后续分析
     */
    public int[] getPalindromeRadii(String s) {
        String t = preprocess(s);
        int n = t.length();
        int[] p = new int[n];
        int center = 0, right = 0;

        for (int i = 1; i < n - 1; i++) {
            int mirror = 2 * center - i;
            if (i < right) {
                p[i] = Math.min(right - i, p[mirror]);
            }
            while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
                p[i]++;
            }
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
        return p;
    }

    /**
     * 统计字符串中回文子串的总数（去重或不去重）
     * 利用 Manacher 的 P 数组：每个位置贡献 P[i] 个以它为中心的回文
     */
    public int countPalindromes(String s) {
        int[] p = getPalindromeRadii(s);
        int count = 0;
        // 从 1 到 n-2 跳过哨兵
        for (int i = 1; i < p.length - 1; i++) {
            count += (p[i] + 1) / 2; // 每个半径对应实际回文子串的数量
        }
        return count;
    }

    public static void main(String[] args) {
        ManacherAlgorithm solution = new ManacherAlgorithm();

        String[] testCases = {
            "babad",
            "cbbd",
            "a",
            "ac",
            "racecar",
            "abacdfgdcaba",
            "aaaa",
            "abcbaabcba"
        };

        System.out.println("=== Manacher 算法测试 ===\n");
        for (String tc : testCases) {
            String result = solution.longestPalindrome(tc);
            int[] radii = solution.getPalindromeRadii(tc);
            int count = solution.countPalindromes(tc);
            System.out.printf("输入: %-15s -> 最长回文: %-10s | 回文总数: %d%n",
                "\"" + tc + "\"", "\"" + result + "\"", count);
            System.out.println("  半径数组: " + Arrays.toString(radii));
            System.out.println();
        }

        // 大规模性能测试
        System.out.println("=== 性能测试 ===");
        StringBuilder large = new StringBuilder();
        for (int i = 0; i < 100000; i++) {
            large.append((char) ('a' + (i % 26)));
        }
        String largeStr = large.toString();

        long startTime = System.currentTimeMillis();
        String result = solution.longestPalindrome(largeStr);
        long endTime = System.currentTimeMillis();
        System.out.printf("字符串长度: %d%n", largeStr.length());
        System.out.printf("最长回文长度: %d%n", result.length());
        System.out.printf("耗时: %d ms%n", endTime - startTime);
    }
}

算法执行 trace 示例

以 "abba" 为例，预处理后的字符串为 "^#a#b#b#a#$"：

最终 P[5] = 2 为最大值，对应原串 "abba"。

复杂度分析

Manacher 算法之所以是线性时间，关键在于：每个字符的扩展操作最多导致 right 向右移动一次，而 right 总共最多移动 n 次。因此总体扩展次数是 O(n) 的。

应用场景与扩展

1. DNA 序列分析：寻找基因片段中的回文结构，某些限制性内切酶的识别位点就是回文序列。
2. 中文分词与校对：回文检测可用于特定语言现象的识别。
3. 回文子串计数：利用 P 数组可在 O(n) 内统计所有回文子串数量。
4. 最长双回文子串：结合后缀数组或 Manacher 的扩展应用。

总结

从中心扩展法的 O(n²) 到 Manacher 的 O(n)，核心突破在于利用已计算信息减少重复工作。这种”以空间换时间”并充分挖掘问题对称性的思路，在算法设计中具有普遍借鉴意义。

Manacher 算法代码简洁、效率极致，是字符串处理领域的经典范例。掌握它，不仅能解决最长回文子串问题，更能深化对”对称性”与”动态边界”的理解。