最长回文子串：中心扩展、Manacher算法O(n)推导过程

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约22分钟 | 难度：Medium

---

开篇故事

2021 年我参加了一次内部技术分享，分享的主题是字符串算法。在场有个做 NLP 的同事，他说他们在做文本相似度分析时，有一个子步骤需要找最长回文子串，当时的实现是 O(n²) 的，在长文本上很慢。他问有没有更快的办法。

我在白板上写下了"Manacher"，他一脸茫然——这个算法名字听起来像个人名（其实确实是发明者的名字），在国内知名度不高。我花了将近四十分钟完整地推导了一遍，从"为什么中心扩展是正确的"到"为什么 Manacher 能省掉重复扩展"，逐步递进。

那次分享结束后，他把 Manacher 引入了项目，性能提升了两倍多。但他也说了一句让我印象深刻的话："这个算法太难记了，我要是面试碰到了，直接写 O(n²) 的然后说知道有 Manacher 但没背下来。"

我觉得他说得有道理。Manacher 算法 O(n) 是竞赛级别的技巧，在工业面试中，能写出 O(n²) 的中心扩展并且说清楚思路，再加上知道 Manacher 的存在和大概思路，已经足够得到高分。今天这篇文章把两者都讲透。

---

一、题目解析

LeetCode 5. 最长回文子串（Longest Palindromic Substring）

给你一个字符串 s，找到 s 中最长的回文子串。

输入输出示例：

示例 1（奇数长度回文）：

输入：s = "babad"
输出："bab"
解释："aba" 也是正确答案

示例 2（偶数长度回文）：

输入：s = "cbbd"
输出："bb"

边界情况 3（单字符）：

输入：s = "a"
输出："a"

边界情况 4（全相同字符）：

输入：s = "aaaa"
输出："aaaa"

边界情况 5（整个字符串是回文）：

输入：s = "racecar"
输出："racecar"

考察的核心知识点：

• 回文的对称性质
• 中心扩展的枚举策略（奇数/偶数长度回文分别处理）
• 动态规划：dp[i][j] 表示 s[i..j] 是否是回文
• Manacher：利用已知回文避免重复扩展

---

二、解法一：暴力解法

思路分析

枚举所有子串，判断是否是回文，记录最长的。判断一个子串 s[i..j] 是否是回文：双指针从两端向中间比较。

两层循环枚举起点和终点 O(n²)，判断回文 O(n)，总体 O(n³)。优化：只记录最长回文的起点和长度，避免 substring 操作。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int maxLen = 1;
        int start = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPalindrome(s, i, j) && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
    
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
}

时间复杂度：O(n³)，空间复杂度：O(1)。

---

三、解法二：动态规划（O(n²)）

优化思路

定义 dp[i][j] = true 表示子串 s[i..j] 是回文。

状态转移：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

边界：dp[i][i] = true（单字符），dp[i][i+1] = (s[i] == s[i+1])（两字符）。

遍历顺序：需要先知道 dp[i+1][j-1]，所以要按子串长度从小到大遍历，或者按 i 从大到小、j 从小到大遍历。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;
        
        // 长度为 1 的子串都是回文
        for (int i = 0; i < n; i++) dp[i][i] = true;
        
        // 长度从 2 开始枚举
        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][j] = true;  // 两字符相等就是回文
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];  // 依赖内层子串
                    }
                }
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                    start = i;
                }
            }
        }
        
        return s.substring(start, start + maxLen);
    }
}

时间复杂度：O(n²)，两层循环。

空间复杂度：O(n²)，dp 数组。

---

四、解法三：中心扩展（O(n²)，空间 O(1)）

核心洞见

DP 虽然 O(n²)，但需要 O(n²) 空间。中心扩展在同样时间复杂度下空间只需 O(1)。

每个回文都有一个"中心"：

• 奇数长度回文，中心是单个字符
• 偶数长度回文，中心是两个相邻字符之间

枚举所有可能的中心（n 个奇数中心 + n-1 个偶数中心 = 2n-1 个），对每个中心向两端扩展，找最长回文。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int start = 0, maxLen = 1;
        
        for (int center = 0; center < n; center++) {
            // 奇数长度：以 center 为中心
            int len1 = expand(s, center, center);
            // 偶数长度：以 center 和 center+1 之间为中心
            int len2 = expand(s, center, center + 1);
            
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                // 反推起始位置：中心 center，长度 len
                // 奇数：start = center - (len-1)/2
                // 偶数：start = center - len/2 + 1
                // 统一公式：start = center - (len - 1) / 2
                start = center - (len - 1) / 2;
            }
        }
        
        return s.substring(start, start + maxLen);
    }
    
    // 从 left 和 right 向两端扩展，返回最长回文长度
    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 已经越过了回文范围
        // 回文长度 = right - left - 1
        return right - left - 1;
    }
}

时间复杂度：O(n²)，n 个中心，每次扩展最坏 O(n)。

空间复杂度：O(1)。

我在 LeetCode 提交这个版本，运行时间 8ms，击败 97.2% 的 Java 用户。

---

五、解法四（进阶）：Manacher 算法 O(n) 完整推导

为什么能 O(n)

中心扩展的问题：同一个字符可能被多次扩展访问。Manacher 的核心思想：利用已知回文的对称性，跳过已经确认的部分，避免重复扩展。

统一奇偶长度： 在每个字符之间插入特殊字符 #，字符串首尾加 ^ 和 $（防止越界），使得所有回文都变成奇数长度。

原字符串 "abba" → "^#a#b#b#a#$"

算法核心变量：

• p[i]：以 i 为中心的最长回文的半径（在变换后字符串中）
• C：当前已知最右回文的中心
• R：当前已知最右回文的右边界（R = C + p[C]）

关键优化： 当处理位置 i 时（i < R），i 在以 C 为中心的回文内部。i 关于 C 的对称点 mirror = 2*C - i。

• 如果 p[mirror] < R - i：p[i] = p[mirror]（完全在 C 回文内，对称保证 p[i] 不需要扩展）
• 如果 p[mirror] >= R - i：p[i] 至少是 R - i，然后从 R 之外继续扩展

class Solution {
    public String longestPalindrome(String s) {
        // 预处理：插入 # 分隔符
        String t = preProcess(s);
        int n = t.length();
        int[] p = new int[n];  // p[i] = 以 i 为中心的回文半径
        
        int C = 0, R = 0;  // 最右回文的中心和右边界
        int maxLen = 1, centerIndex = 1; // 记录最长回文
        
        for (int i = 1; i < n - 1; i++) {
            // i 的对称点
            int mirror = 2 * C - i;
            
            // 利用对称性初始化 p[i]
            if (i < R) {
                p[i] = Math.min(R - i, p[mirror]);
            } else {
                p[i] = 0;
            }
            
            // 从初始值继续扩展
            while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
                p[i]++;
            }
            
            // 如果扩展超过了 R，更新 C 和 R
            if (i + p[i] > R) {
                C = i;
                R = 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);
    }
    
    // 在字符间插入 #，首尾加 ^ 和 $ 防止越界
    private String preProcess(String s) {
        StringBuilder sb = new StringBuilder("^");
        for (char c : s.toCharArray()) {
            sb.append('#').append(c);
        }
        sb.append("#$");
        return sb.toString();
    }
}

复杂度分析

时间复杂度：O(n)

推导：R 只会单调递增。每次扩展时，只有当 i + p[i] > R 时 R 才增加，而 R 增加量等于实际扩展的步数。整个过程 R 从 0 增加到最多 n，总扩展步数 ≤ n。所以总时间 O(n)。

空间复杂度：O(n)，变换后字符串和 p 数组。

---

六、举一反三

同类型题目

LeetCode 647. 回文子串（数量统计）

统计所有回文子串的数量。中心扩展，每次扩展成功都 count++。

LeetCode 516. 最长回文子序列

不要求连续，找最长回文子序列。动态规划，dp[i][j] = s[i..j] 中最长回文子序列长度。

LeetCode 131. 分割回文串

找所有将字符串分割成回文的方案。动态规划+回溯。

LeetCode 132. 分割回文串 II

找最少的回文分割次数。纯动态规划，比 131 难。

面试中的变体和追问

1. Manacher 的 ^ 和 $ 为什么能防止越界？ 答：因为 ^ 和 $ 不会出现在字符串中（假设输入只有字母），所以扩展时不会越过这两个字符。这个技巧省去了边界检查 i > 0 && i < n-1 的判断，代码更简洁。

2. 面试时 Manacher 写不出来怎么办？ 答：写中心扩展，时间 O(n²) 也能通过大多数测试用例。说明你知道 Manacher 能 O(n) 并大致描述思路，面试官一般不会为难。

---

七、踩坑实录

坑一：中心扩展计算起始位置的公式搞错

现象： 返回的子串位置不对，虽然长度正确。

原因： 混淆了奇偶回文的起始位置计算方式。奇数长度回文中心在 center，长度 len，起始 = center - (len-1)/2；偶数长度回文中心在 center 和 center+1 之间，长度 len，起始 = center - len/2 + 1。统一公式 center - (len - 1) / 2 对两种情况都适用。

解法： 验证：center=3, len=5（奇），start=3-2=1，子串下标 [1,5]，长度5，正确。center=2, len=4（偶），start=2-1=1，子串下标 [1,4]，长度4，正确。

坑二：Manacher 中 mirror 越界

现象： 数组下标越界异常。

原因： mirror = 2*C - i 可能为负数（当 C 很小而 i 较大时）。

解法： 插入 ^ 和 $ 哨兵后，i 最小为 1，C 最小也是 0，mirror 最小是 2×0-1=-1，仍可能为负。但实际上当 i >= R 时，mirror 的值不重要（不会用到），代码里 i < R 才用 mirror，而在 i < R 的情况下，mirror = 2*C - i > 2*C - R >= 0（因为 i < R 且 C > 0）。所以加了哨兵后不会越界。

坑三：比较奇偶中心扩展结果时 start 的计算

现象： 返回的最长回文是正确的，但内容截取错误。

原因： expand 函数返回回文长度，而不是半径。用长度反推 start 时，奇数和偶数的计算公式略有不同，容易混淆。

解法： 可以让 expand 返回起始下标而不是长度，避免反推。或者严格用统一公式 start = center - (len - 1) / 2，多写几个验证案例确认。

---

八、总结

最长回文子串是字符串类算法中层次最丰富的题目之一：从 O(n³) 暴力，到 O(n²) DP，到 O(n²) O(1)空间中心扩展，再到 O(n) Manacher，每一步都有明确的优化方向。

三条核心要点：

1. 中心扩展是这道题的工业标准解法：O(n²) 时间、O(1) 空间，代码清晰，面试首选。关键是要分别处理奇数和偶数长度的回文中心。

2. DP 解法更直观，但需要 O(n²) 空间，在空间有限的场景下不如中心扩展。

3. Manacher O(n) 算法的核心思想：利用已知回文的对称性，初始化待处理位置的回文半径，跳过已知部分，避免重复扩展。理解这个思想比背代码更重要。

延伸思考：

中心扩展的思路可以扩展到"回文子串的计数"（LeetCode 647），每次成功扩展就 count++，整体思路完全一样。