每日算法 — 使用java实现马拉车算法：线性时间回文子串查找

问题引入

回文子串查找是字符串处理中的基础问题。给定一个字符串，要求找出其中最长的回文子串。暴力解法需要O(N^3)时间，中心扩展法优化到O(N^2)，而Manacher算法（中文常译为马拉车算法）能在O(N)时间内完成求解，且实现简洁。本文用Java完整实现马拉车算法，并深入讲解其对称扩展的核心思想。

算法原理

预处理

原始字符串中回文子串的长度可能是奇数也可能是偶数。马拉车算法通过在每个字符间插入一个不会出现在原串中的分隔符（如#），将问题统一转化为寻找奇数长度回文。例如 "abba" 变为 "#a#b#b#a#"，原串中的偶回文对应新串中的奇回文。

对称扩展与镜像复用

维护一个当前已知最右回文子串的右边界right及其中心center。对于位置i，如果i < right，则i关于center的对称点mirror = 2 * center - i的回文半径p[mirror]可以直接复用，因为对称性保证了i周围至少存在长度为p[mirror]的回文。随后只需要从right继续向外扩展验证即可。如果i >= right，则只能暴力扩展。

完整Java实现

package algorithm.manacher;

/**
 * 马拉车算法（Manacher）
 * 线性时间O(N)查找最长回文子串
 */
public class ManacherAlgorithm {

    /**
     * 查找最长回文子串
     * @param s 输入字符串
     * @return 最长回文子串
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        // 预处理：插入分隔符，统一为奇数长度回文
        char[] t = preprocess(s);
        int n = t.length;
        int[] p = new int[n]; // p[i]表示以i为中心的回文半径（含中心）

        int center = 0; // 当前最右回文的中心
        int right = 0;  // 当前最右回文的右边界（不含）
        int maxLen = 0; // 最大回文长度
        int centerIndex = 0; // 最大回文的中心索引

        for (int i = 0; i < n; i++) {
            // 利用对称性确定初始回文半径
            int mirror = 2 * center - i;
            if (i < right) {
                // p[mirror]是镜像点的半径，但不能超过right-i的剩余长度
                p[i] = Math.min(right - i, p[mirror]);
            }

            // 中心扩展：尝试继续扩大以i为中心的回文
            int a = i + (1 + p[i]); // 右侧尝试扩展位置
            int b = i - (1 + p[i]); // 左侧尝试扩展位置
            while (b >= 0 && a < n && t[a] == t[b]) {
                p[i]++;
                a++;
                b--;
            }

            // 更新最右回文边界
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }

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

        // 从预处理串中还原原串的回文子串
        int start = (centerIndex - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }

    /**
     * 预处理字符串，在每个字符间插入'#'，并在首尾添加哨兵
     * 例如 "abba" -> "^#a#b#b#a#$"
     */
    private char[] preprocess(String s) {
        int n = s.length();
        char[] t = new char[n * 2 + 3];
        t[0] = '^';
        t[n * 2 + 2] = '$';
        for (int i = 0; i < n; i++) {
            t[i * 2 + 1] = '#';
            t[i * 2 + 2] = s.charAt(i);
        }
        t[n * 2 + 1] = '#';
        return t;
    }

    /**
     * 查找所有回文子串的数量（允许重叠）
     */
    public int countPalindromicSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;

        char[] t = preprocess(s);
        int n = t.length;
        int[] p = new int[n];
        int center = 0, right = 0;
        int count = 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[i + (1 + p[i])] == t[i - (1 + p[i])]) {
                p[i]++;
            }

            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }

            // 每个位置贡献的回文子串数量等于回文半径
            count += p[i];
        }

        return count;
    }

    /**
     * 批量测试
     */
    public static void main(String[] args) {
        ManacherAlgorithm solver = new ManacherAlgorithm();

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

        System.out.println("=== 最长回文子串测试 ===");
        for (String test : testCases) {
            String result = solver.longestPalindrome(test);
            System.out.printf("输入: %-20s -> 最长回文: %s%n", "\"" + test + "\"", result);
        }

        System.out.println("\n=== 回文子串计数测试 ===");
        for (String test : testCases) {
            int count = solver.countPalindromicSubstrings(test);
            System.out.printf("输入: %-20s -> 回文数量: %d%n", "\"" + test + "\"", count);
        }
    }
}

复杂度分析

马拉车算法的线性时间保证来自于每个字符最多被访问常数次。当i < right时，直接利用镜像结果避免重复扩展；当需要扩展时，扩展的结果会推动right右移，而right在整个算法过程中只增不减，因此总扩展次数为O(N)。

关键技巧总结

• 分隔符预处理将偶回文和奇回文统一为奇回文，大幅简化逻辑
• mirror = 2 * center - i 是对称点坐标计算的核心公式
• p[mirror]不能直接复用，需取 min(right - i, p[mirror]) 防止越界
• 哨兵字符 ^ 和 $ 可避免边界检查，提升代码简洁性