引言
回文（Palindrome） 是字符串算法中的经典问题。给定字符串 "abacaba"，它的最长回文子串是 "abacaba" 本身；而对于 "babad"，最长回文子串是 "bab" 或 "aba"。
朴素的中心扩展法需要 O(n²) 时间，而 Manacher 算法 由 Glenn Manacher 于 1975 年提出，能够在 O(n) 线性时间内找出字符串的所有回文子串，并确定最长回文子串的长度和位置。
本文将用 Java 完整实现 Manacher 算法，深入讲解其对称性利用的巧妙设计，并展示在实际问题中的应用。
算法原理
中心扩展法的瓶颈
中心扩展法对每个可能的中心点向两边扩展，直到不再回文：
– 奇数长度回文的中心是一个字符（如 "aba" 的中心是 'b'）
– 偶数长度回文的中心是两个字符之间（如 "abba" 的中心在 'bb' 中间）
这意味着有 2n - 1 个中心点，每个最坏扩展 O(n) 次，总复杂度 O(n²)。
Manacher 的核心洞察
Manacher 算法的核心在于利用已计算出的回文信息来避免重复计算。假设我们已经知道以某个中心点 C 为中心的回文半径，那么对于该中心右侧的一个点 i，它的对称点 mirror = 2*C - i 在中心左侧。如果 mirror 的回文完全包含在 C 的回文内，那么 i 的回文至少和 mirror 一样长。
三个关键变量
P[i]：以位置i为中心的回文半径（向单侧扩展的长度，包含中心）C：当前已知回文右边界最远的中心点R：C的回文右边界（R = C + P[C]）
对称点计算
对于当前处理的位置 i，其关于中心 C 的对称点为：
mirror = 2 * C - i
边界情况
即使 mirror 的回文可以利用，也需要考虑 i + P[mirror] 是否超过 R：
– 如果 i + P[mirror] < R：P[i] = P[mirror]（完全对称，直接复用）
– 如果 i + P[mirror] >= R：P[i] = R - i（至少到 R，需要继续扩展验证）
统一奇偶处理
Manacher 的经典技巧是在字符串的每个字符之间插入一个不会在原串中出现的分隔符（如 '#'），并在首尾添加不同的边界标记。这样，所有回文都变成了奇数长度，无需分别处理奇偶两种情况。
例如："abba" → "^#a#b#b#a#$"
Java 实现
1. 标准 Manacher 算法
/**
* Manacher算法标准实现
* 线性时间O(n)找出最长回文子串
*/
public class ManacherAlgorithm {
/**
* Manacher算法的核心方法
* @param s 输入字符串
* @return 包含最长回文长度、起始位置等信息的结果对象
*/
public ManacherResult findLongestPalindrome(String s) {
if (s == null || s.length() == 0) {
return new ManacherResult(0, 0, 0, new int[0]);
}
// Step 1: 预处理，插入分隔符
// 原串 "abba" -> "^#a#b#b#a#$"
char[] processed = preprocess(s);
int n = processed.length;
// P[i] 表示以 processed[i] 为中心的回文半径
// 实际回文长度为 P[i] - 1（因为包含了分隔符）
int[] P = new int[n];
int C = 0; // 当前回文右边界最远的中心
int R = 0; // 当前已知最右回文边界
int maxLen = 0; // 最长回文长度
int centerIndex = 0; // 最长回文的中心位置
// Step 2: 线性扫描
for (int i = 1; i < n - 1; i++) {
// 计算i关于C的对称点
int mirror = 2 * C - i;
// 如果i在当前最右边界内，可以利用对称信息
if (i < R) {
// P[mirror]是已知的，但i+P[mirror]不能超过R
P[i] = Math.min(R - i, P[mirror]);
}
// 尝试继续扩展（无论是否利用了对称信息，都需要扩展验证）
// 以i为中心，向两边扩展
while (processed[i + (1 + P[i])] == processed[i - (1 + P[i])]) {
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;
}
}
// Step 3: 从处理后的字符串还原原串的位置
// 最长回文在原串中的起始位置
int start = (centerIndex - maxLen) / 2;
return new ManacherResult(maxLen - 1, start, centerIndex, P);
}
/**
* 预处理字符串：插入'#'分隔符，并添加边界标记
* "abc" -> "^#a#b#c#$"
*/
private char[] preprocess(String s) {
int n = s.length();
char[] result = new char[n * 2 + 3];
result[0] = '^'; // 左边界，保证不会匹配
result[n * 2 + 2] = '$'; // 右边界，保证不会匹配
for (int i = 0; i < n; i++) {
result[i * 2 + 1] = '#';
result[i * 2 + 2] = s.charAt(i);
}
result[n * 2 + 1] = '#';
return result;
}
/**
* 结果封装类
*/
public static class ManacherResult {
public final int length; // 最长回文子串长度
public final int startIndex; // 在原串中的起始位置
public final int centerIndex; // 在预处理串中的中心位置
public final int[] radii; // 所有位置的回文半径数组
public ManacherResult(int length, int startIndex, int centerIndex, int[] radii) {
this.length = length;
this.startIndex = startIndex;
this.centerIndex = centerIndex;
this.radii = radii;
}
@Override
public String toString() {
return String.format("最长回文长度=%d, 起始位置=%d, 中心位置=%d",
length, startIndex, centerIndex);
}
}
}
2. 扩展应用类
/**
* 基于Manacher算法的扩展功能
* 包括：统计回文子串数量、找出所有回文中心、最短回文超串等
*/
public class ManacherExtensions {
private final int[] P;
private final String original;
private final int n;
public ManacherExtensions(String s) {
this.original = s;
ManacherAlgorithm manacher = new ManacherAlgorithm();
ManacherAlgorithm.ManacherResult result = manacher.findLongestPalindrome(s);
this.P = result.radii;
this.n = P.length;
}
/**
* 统计原字符串中回文子串的总数
* 每个位置i的P[i]表示该中心的回文半径，对应的回文子串数量为 P[i] / 2（向下取整）
*/
public long countPalindromicSubstrings() {
long count = 0;
// 跳过边界标记 ^ 和 $
for (int i = 1; i < n - 1; i++) {
// P[i] 是包含分隔符的半径，实际回文数量为 P[i] / 2
count += P[i] / 2;
}
return count;
}
/**
* 找出所有回文子串的中心位置（在原串中的索引）
* @return 每个回文子串的 [起始位置, 结束位置] 列表
*/
public java.util.List<int[]> findAllPalindromes() {
java.util.List<int[]> palindromes = new java.util.ArrayList<>();
for (int i = 1; i < n - 1; i++) {
int radius = P[i];
// 中心在原串中的位置
int centerInOriginal = (i - 1) / 2;
// 遍历以i为中心的所有回文
for (int r = 1; r < radius; r++) {
int len = r; // 单侧扩展长度
// 奇数长度回文
if (i % 2 == 0) { // 中心在字符上
int start = centerInOriginal - (len - 1) / 2;
int end = centerInOriginal + len / 2;
if (start >= 0 && end < original.length()) {
palindromes.add(new int[]{start, end});
}
}
}
}
return palindromes;
}
/**
* 检查子串 [l, r] 是否为回文
* 利用Manacher预处理结果实现O(1)查询
*/
public boolean isPalindrome(int l, int r) {
// 将原串位置转换为处理串中的中心位置
int center = l + r + 2; // 在预处理串中的索引
int requiredRadius = r - l + 1;
return center < n && P[center] >= requiredRadius;
}
/**
* 计算以每个位置结尾的最长回文后缀长度
* 用于构建最短回文超串
*/
public int[] longestPalindromicSuffix() {
int m = original.length();
int[] suffixLen = new int[m];
for (int i = 0; i < m; i++) {
// 在预处理串中对应的位置
int processedIdx = 2 * i + 2;
// 向两边扩展的最远距离
int radius = P[processedIdx];
// 如果以i结尾的回文能延伸到开头
if (processedIdx - radius + 1 <= 1) {
suffixLen[i] = i + 1;
} else {
suffixLen[i] = (radius - 1) * 2 + 1;
// 需要修正偶数长度的情况
if (processedIdx % 2 == 0) {
suffixLen[i] = Math.min(suffixLen[i], (i + 1) * 2 - 1);
}
}
}
return suffixLen;
}
/**
* 构建最短回文超串
* 在字符串末尾添加最少字符使其成为回文
* 例如 "abc" -> "abcba"
*/
public String shortestPalindromeSuperstring() {
// 找到以最后一个字符结尾的最长回文后缀
int lastIdx = original.length() - 1;
int processedIdx = 2 * lastIdx + 2;
int maxPalSuffix = 0;
for (int i = 1; i < n - 1; i++) {
int radius = P[i];
int rightBoundary = i + radius - 1;
// 如果回文能延伸到最右端
if (rightBoundary >= n - 2) {
int len;
if (i % 2 == 0) {
// 中心在字符上，奇数长度
len = (n - 2 - i) * 2 + 1;
} else {
// 中心在分隔符上，偶数长度
len = (n - 2 - i) * 2;
}
maxPalSuffix = Math.max(maxPalSuffix, len);
}
}
// 需要添加的字符是前缀的逆序（去掉回文部分）
int prefixToAdd = original.length() - maxPalSuffix;
StringBuilder sb = new StringBuilder(original);
for (int i = prefixToAdd - 1; i >= 0; i--) {
sb.append(original.charAt(i));
}
return sb.toString();
}
}
3. 完整测试与演示
/**
* Manacher算法完整测试
*/
public class ManacherDemo {
public static void main(String[] args) {
ManacherAlgorithm manacher = new ManacherAlgorithm();
// 测试用例1：奇数长度回文
String s1 = "abacaba";
ManacherAlgorithm.ManacherResult r1 = manacher.findLongestPalindrome(s1);
System.out.println("输入: \"" + s1 + "\"");
System.out.println("结果: " + r1);
System.out.println("最长回文子串: \"" + s1.substring(r1.startIndex, r1.startIndex + r1.length) + "\"");
System.out.println();
// 测试用例2：偶数长度回文
String s2 = "abba";
ManacherAlgorithm.ManacherResult r2 = manacher.findLongestPalindrome(s2);
System.out.println("输入: \"" + s2 + "\"");
System.out.println("结果: " + r2);
System.out.println("最长回文子串: \"" + s2.substring(r2.startIndex, r2.startIndex + r2.length) + "\"");
System.out.println();
// 测试用例3：无长回文
String s3 = "abcd";
ManacherAlgorithm.ManacherResult r3 = manacher.findLongestPalindrome(s3);
System.out.println("输入: \"" + s3 + "\"");
System.out.println("结果: " + r3);
System.out.println("最长回文子串: \"" + s3.substring(r3.startIndex, r3.startIndex + r3.length) + "\"");
System.out.println();
// 测试用例4：复杂字符串
String s4 = "babad";
ManacherAlgorithm.ManacherResult r4 = manacher.findLongestPalindrome(s4);
System.out.println("输入: \"" + s4 + "\"");
System.out.println("结果: " + r4);
System.out.println("最长回文子串: \"" + s4.substring(r4.startIndex, r4.startIndex + r4.length) + "\"");
System.out.println();
// 扩展功能测试
System.out.println("=== 扩展功能测试 ===");
ManacherExtensions ext = new ManacherExtensions("aaa");
System.out.println("\"aaa\" 的回文子串数量: " + ext.countPalindromicSubstrings());
// 期望: "a"(3个) + "aa"(2个) + "aaa"(1个) = 6
ManacherExtensions ext2 = new ManacherExtensions("abcba");
System.out.println("\"abcba\" 的回文子串数量: " + ext2.countPalindromicSubstrings());
// 最短回文超串
ManacherExtensions ext3 = new ManacherExtensions("abc");
System.out.println("\"abc\" 的最短回文超串: \"" + ext3.shortestPalindromeSuperstring() + "\"");
// 期望: "abcba"
ManacherExtensions ext4 = new ManacherExtensions("aacecaaa");
System.out.println("\"aacecaaa\" 的最短回文超串: \"" + ext4.shortestPalindromeSuperstring() + "\"");
// 期望: "aaacecaaa"
// 大规模性能测试
System.out.println("\n=== 性能测试 ===");
StringBuilder large = new StringBuilder();
for (int i = 0; i < 1000000; i++) {
large.append((char) ('a' + (i % 26)));
}
String largeStr = large.toString();
long start = System.currentTimeMillis();
manacher.findLongestPalindrome(largeStr);
long end = System.currentTimeMillis();
System.out.println("100万字符处理耗时: " + (end - start) + "ms");
}
}
4. 结合动态规划的进阶应用
/**
* Manacher + DP：回文分割问题
* 将字符串分割成最少个数的回文子串
*/
public class PalindromePartition {
/**
* 最少回文分割
* 先用Manacher预处理所有回文信息，再用DP求解
*/
public int minCut(String s) {
if (s == null || s.length() <= 1) return 0;
int n = s.length();
ManacherAlgorithm manacher = new ManacherAlgorithm();
ManacherAlgorithm.ManacherResult result = manacher.findLongestPalindrome(s);
int[] P = result.radii;
// dp[i] 表示 s[0..i] 的最少分割次数
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = i; // 最坏情况：每个字符单独分割
}
// 利用Manacher结果优化：对于每个回文中心，更新DP
int processedLen = P.length;
for (int i = 1; i < processedLen - 1; i++) {
int radius = P[i];
// 以i为中心的所有回文
for (int r = 1; r < radius; r++) {
int left, right;
if (i % 2 == 0) {
// 奇数长度回文，中心在字符上
int center = (i - 2) / 2;
left = center - (r - 1) / 2;
right = center + (r - 1) / 2;
} else {
// 偶数长度回文，中心在分隔符上
int leftCenter = (i - 1) / 2;
left = leftCenter - r / 2 + 1;
right = leftCenter + r / 2;
}
if (left >= 0 && right < n && left <= right) {
if (left == 0) {
dp[right] = 0; // s[0..right]本身就是回文
} else {
dp[right] = Math.min(dp[right], dp[left - 1] + 1);
}
}
}
}
return dp[n - 1];
}
public static void main(String[] args) {
PalindromePartition solver = new PalindromePartition();
System.out.println("\"aab\" 最少分割: " + solver.minCut("aab")); // 1: "aa"|"b"
System.out.println("\"abcba\" 最少分割: " + solver.minCut("abcba")); // 0
System.out.println("\"abcbm\" 最少分割: " + solver.minCut("abcbm")); // 2
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 预处理 | O(n) | O(n) | 插入分隔符 |
| Manacher主算法 | O(n) | O(n) | 线性扫描，每个位置最多被扩展一次 |
| 统计回文数量 | O(n) | O(1) | 基于P数组遍历 |
| 回文判断查询 | O(1) | O(1) | 预处理后直接查表 |
| 最短回文超串 | O(n) | O(n) | 利用Manacher结果一次遍历 |
| 最少回文分割 | O(n) | O(n) | DP + Manacher优化 |
均摊分析：算法中的 while 扩展循环看似可能执行很多次，但注意到 R（最右边界）只会向右移动，总共最多移动 n 次。因此所有扩展操作的总次数是 O(n)。
应用场景
1. DNA 序列分析
在生物信息学中，回文序列具有重要的生物学意义（如限制性内切酶的识别位点）。Manacher 可以高效地在长 DNA 序列中查找所有回文模式。
2. 文本编辑器的回文检测
实现”查找文档中所有回文”的功能，Manacher 的 O(n) 复杂度可以实时处理大文档。
3. 压缩算法
某些基于回文的压缩算法（如回文替换编码）需要快速定位所有回文子串。
4. 验证码生成
生成对称美观的验证码文本时，可以利用回文性质。
常见误区
- P[i] 的含义：
P[i]是预处理串中的半径（包含分隔符），实际回文长度为P[i] - 1 - 边界处理：
^和$边界标记确保不会越界，但在实际实现中也可以使用边界检查替代 - 偶数回文的转换：插入
'#'后，原串的偶数回文变成了以'#'为中心的奇数回文
总结
Manacher 算法是字符串算法中的经典之作，它通过对称性复用将回文查找的复杂度从 O(n²) 降到 O(n)。本文的 Java 实现展示了：
- 预处理技巧：插入分隔符统一奇偶处理
- 对称点计算：
mirror = 2*C - i的核心公式 - 边界复用：
P[i] = min(R-i, P[mirror])的巧妙判断 - 扩展应用：回文计数、超串构造、分割优化等
对于任何涉及回文子串的问题，Manacher 算法都是首选的高效解决方案。
