每日算法 — 使用java实现Manacher：线性时间最长回文子串的镜像扩展

算法概述

Manacher算法由Glenn Manacher于1975年提出，用于在线性时间O(n)内找出字符串中的所有回文子串，或求解最长回文子串问题。相比中心扩展法的O(n²)和动态规划的O(n²)，Manacher算法将时间复杂度降至线性，是字符串处理领域的经典算法。

该算法的核心思想是利用回文的对称性：若已知一个回文中心及其右边界，则其右侧部分字符的回文信息可以通过对称位置的信息快速推导，避免重复计算。

核心原理

回文半径与预处理

对于字符串中的每个位置i，定义回文半径p[i]为以i为中心的最长回文子串的半径（包含中心字符）。

为了统一处理奇偶长度回文，先对字符串进行预处理：在每个字符之间及两端插入分隔符（如’#’）。

例如：”abba” → “#a#b#b#a#”

这样所有回文都变为奇数长度，中心唯一确定。

镜像对称加速

维护当前最右回文的中心c和右边界r。对于位置i：

1. i在r左侧：设i关于c的对称点为mirror = 2c – i
2. 若p[mirror]的扩展不超过r，则p[i] = p[mirror]（直接镜像）

3. 否则p[i]至少为r – i，需要继续向右扩展验证

4. i在r右侧或边界：p[i] = 1，然后向右扩展

5. 更新最右边界：若i + p[i] > r，更新c = i，r = i + p[i]

核心不变式

始终维护c和r使得以c为中心的回文子串右边界最远。利用此信息为后续位置提供下界估计。

Java完整实现

/**
 * Manacher算法：线性时间求解最长回文子串
 * 利用回文对称性避免重复计算
 */
public class Manacher {

    /**
     * 预处理字符串：插入分隔符统一奇偶长度
     * "abba" -> "#a#b#b#a#"
     * @param s 原始字符串
     * @return 预处理后的字符数组
     */
    private static char[] preprocess(String s) {
        int n = s.length();
        char[] t = new char[2 * n + 3];
        t[0] = '^';  // 开头哨兵，防止越界
        t[1] = '#';
        for (int i = 0; i < n; i++) {
            t[2 * i + 2] = s.charAt(i);
            t[2 * i + 3] = '#';
        }
        t[2 * n + 2] = '$';  // 结尾哨兵
        return t;
    }

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

        char[] t = preprocess(s);
        int n = t.length;
        int[] p = new int[n];  // 回文半径数组

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

        for (int i = 1; i < n - 1; i++) {
            // 利用对称性获取初始半径下界
            int mirror = 2 * center - i;  // i关于center的对称点

            if (i < right) {
                // i在当前最右回文内部，利用对称性
                p[i] = Math.min(right - i, p[mirror]);
            } else {
                // i在最右回文右侧，从1开始扩展
                p[i] = 1;
            }

            // 中心扩展：尝试向两边扩展回文
            while (t[i + p[i]] == t[i - p[i]]) {
                p[i]++;
            }

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

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

        // 从预处理字符串中提取原始回文子串
        // 起始位置：(centerIndex - maxLen + 1 - 1) / 2 = (centerIndex - maxLen) / 2
        int start = (centerIndex - maxLen) / 2;
        return s.substring(start, start + maxLen - 1);
    }

    /**
     * 求解所有回文子串的数量
     * 每个不同的回文子串只计数一次
     */
    public static 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]);
            } else {
                p[i] = 1;
            }

            while (t[i + p[i]] == t[i - p[i]]) {
                p[i]++;
            }

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

            // 以i为中心的回文子串数量为 p[i] / 2（向下取整）
            count += p[i] / 2;
        }

        return count;
    }

    /**
     * 获取以每个位置为中心的最长回文半径
     * 可用于后续回文相关查询
     */
    public static int[] getPalindromeRadii(String s) {
        char[] 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]);
            } else {
                p[i] = 1;
            }

            while (t[i + p[i]] == t[i - p[i]]) {
                p[i]++;
            }

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

        return p;
    }

    /**
     * 判断子串s[l..r]是否为回文（O(1)查询，需先预处理）
     */
    public static boolean isPalindromeQuery(int[] radii, int l, int r) {
        // 预处理后的位置：字符s[i]对应t[2*i+2]
        // 子串s[l..r]对应中心在t[l+r+2]
        int center = l + r + 2;
        int radius = r - l + 1;
        return radii[center] >= radius + 1;  // 包含#的半径条件
    }

    /**
     * 寻找最长双回文串（由两个回文拼接而成）
     */
    public static String longestDoublePalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

        int[] radii = getPalindromeRadii(s);
        int maxLen = 0;
        int split = 0;

        for (int i = 0; i < n - 1; i++) {
            // 检查s[0..i]和s[i+1..n-1]是否都是回文
            int leftCenter = i + 2;  // t中的中心位置
            int rightCenter = i + 1 + n + 1;

            boolean leftPal = (i % 2 == 0) ? 
                radii[leftCenter] >= i + 2 :
                radii[leftCenter] >= i + 2;

            // 简化：直接调用最长回文
            String left = s.substring(0, i + 1);
            String right = s.substring(i + 1);
            String lp = longestPalindrome(left);
            String rp = longestPalindrome(right);

            if (lp.length() + rp.length() > maxLen) {
                maxLen = lp.length() + rp.length();
                split = i;
            }
        }

        return s.substring(0, split + 1) + s.substring(split + 1);
    }

    /**
     * 主程序：测试Manacher算法
     */
    public static void main(String[] args) {
        System.out.println("===== Manacher最长回文子串算法 =====\n");

        // 测试1：基本回文检测
        System.out.println("--- 测试1：基本回文子串 ---");
        String[] testCases = {
            "babad",           // "bab" 或 "aba"
            "cbbd",            // "bb"
            "a",               // "a"
            "ac",              // "a" 或 "c"
            "racecar",         // "racecar"
            "bananas",         // "anana"
            "abacdfgdcaba",    // "aba"
            "aaaa",            // "aaaa"
            "abcbaabcba",      // "abcbaabcba"
        };

        for (String test : testCases) {
            long start = System.nanoTime();
            String result = longestPalindrome(test);
            long end = System.nanoTime();
            System.out.printf("输入: %-20s -> 最长回文: %-15s (耗时: %dns)%n", 
                "\"" + test + "\"", "\"" + result + "\"", (end - start));
        }

        // 测试2：回文子串计数
        System.out.println("\n--- 测试2：回文子串计数 ---");
        String[] countTests = {"aaa", "abc", "abba", "racecar"};
        for (String test : countTests) {
            int count = countPalindromicSubstrings(test);
            System.out.printf("\"%s\" 中的回文子串数量: %d%n", test, count);
        }

        // 测试3：预处理验证
        System.out.println("\n--- 测试3：预处理字符串 ---");
        String sample = "abba";
        char[] processed = preprocess(sample);
        System.out.println("原始: " + sample);
        System.out.println("预处理后: " + new String(processed));

        // 测试4：大规模性能测试
        System.out.println("\n--- 测试4：大规模性能测试 ---");
        StringBuilder sb = new StringBuilder();
        java.util.Random rand = new java.util.Random(42);
        for (int i = 0; i < 100000; i++) {
            sb.append((char) ('a' + rand.nextInt(26)));
        }
        String large = sb.toString();

        long start = System.currentTimeMillis();
        String largeResult = longestPalindrome(large);
        long manacherTime = System.currentTimeMillis() - start;

        start = System.currentTimeMillis();
        String dpResult = longestPalindromeDP(large);
        long dpTime = System.currentTimeMillis() - start;

        System.out.println("字符串长度: " + large.length());
        System.out.println("Manacher结果长度: " + largeResult.length());
        System.out.println("Manacher耗时: " + manacherTime + "ms");
        System.out.println("DP耗时: " + dpTime + "ms");
        System.out.println("加速比: " + (dpTime / Math.max(manacherTime, 1)) + "x");

        // 测试5：边界情况
        System.out.println("\n--- 测试5：边界情况 ---");
        System.out.println("空字符串: \"" + longestPalindrome("") + "\"");
        System.out.println("单字符: \"" + longestPalindrome("x") + "\"");
        System.out.println("全相同: \"" + longestPalindrome("zzzzzz") + "\"");
        System.out.println("无回文(>1): \"" + longestPalindrome("abcdef") + "\"");
    }

    /**
     * 动态规划版本（O(n²)），用于性能对比
     */
    private static String longestPalindromeDP(String s) {
        int n = s.length();
        if (n < 2) return s;

        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;

        // 单个字符都是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 填充表格
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (len == 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (len > maxLen) {
                            maxLen = len;
                            start = i;
                        }
                    }
                }
            }
        }

        return s.substring(start, start + maxLen);
    }
}

算法执行流程图解

以字符串”abacaba”为例：

预处理: ^#a#b#a#c#a#b#a#$
索引:    0123456789...

i=2 (字符'a'): p[2]=1, 扩展得 p[2]=2（"#a#"）
i=4 (字符'b'): p[4]=1, 扩展得 p[4]=2（"#b#"）
i=6 (字符'a'): 在右边界内，mirror=2, p[6]=min(r-6, p[2])=2, 扩展得 p[6]=4（"#a#b#a#"）
i=8 (字符'c'): 在右边界内，mirror=4, p[8]=min(r-8, p[4])=2, 扩展得 p[8]=8（整个回文）

复杂度分析

扩展应用

回文树（Eertree）

用于统计不同回文子串的数量和出现位置，也是线性时间算法。

回文因子分解

将字符串分解为最少数量的回文子串，可用Manacher预处理结合DP求解。

最长回文子序列

与最长回文子串不同，允许删除字符。需要用动态规划O(n²)求解。

应用场景

1. DNA序列分析：寻找基因组中的回文结构
2. 音乐信息检索：旋律片段的对称性检测
3. 自然语言处理：回文词检测、文本对称性分析
4. 数据压缩：利用回文结构进行编码优化
5. 竞赛编程：字符串类问题的标准工具

总结

Manacher算法通过对称性利用和预处理技巧，将回文子串问题的复杂度降至理论下界O(n)。其核心思想——维护最右回文边界并利用镜像信息——展示了算法设计中”避免重复计算”原则的精妙应用。理解Manacher算法有助于培养将几何直觉转化为高效代码的能力。