DeepSeek 提供一个完整的 **Manacher 算法 Java 实现**，包括详细的注释和测试示例
·
我来提供一个完整的 Manacher 算法 Java 实现，包括详细的注释和测试示例。
1. 完整实现代码
public class ManacherAlgorithm {
/**
* 查找最长回文子串 - Manacher 算法
* @param s 原始字符串
* @return 最长回文子串
*/
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
// 1. 预处理字符串，插入特殊字符 '#'
// 同时添加边界字符 '^' 和 '$' 避免越界判断
char[] T = preprocess(s);
int n = T.length;
// 2. 创建回文半径数组
int[] P = new int[n];
// 3. 当前能延伸到最右端的回文中心及其右边界
int center = 0;
int right = 0;
// 4. 遍历处理后的字符串（跳过边界字符）
for (int i = 1; i < n - 1; i++) {
// i 关于 center 的对称点
int mirror = 2 * center - i;
// 如果 i 在当前最右回文的覆盖范围内
if (i < right) {
// 利用对称性，取 mirror 的回文半径和到右边界的距离的较小值
P[i] = Math.min(right - i, P[mirror]);
}
// 尝试中心扩展
// 注意：T[0]='^', T[n-1]='$' 与任何字符都不相等，保证不会越界
while (T[i + P[i] + 1] == T[i - P[i] - 1]) {
P[i]++;
}
// 如果扩展后的回文右边界超过当前右边界，更新 center 和 right
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
// 5. 找出最长回文子串
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
// 6. 计算原始字符串中的起始位置
int start = (centerIndex - maxLen) / 2;
return s.substring(start, start + maxLen);
}
/**
* 预处理字符串，插入特殊字符 '#'
* 格式：^#a#b#a#$
*/
private static char[] preprocess(String s) {
int n = s.length();
if (n == 0) {
return new char[]{'^', '$'};
}
char[] T = new char[2 * n + 3];
T[0] = '^'; // 起始边界符
T[2 * n + 2] = '$'; // 结束边界符
for (int i = 0; i < n; i++) {
T[2 * i + 1] = '#';
T[2 * i + 2] = s.charAt(i);
}
T[2 * n + 1] = '#';
return T;
}
/**
* 扩展版本：返回所有信息，包括最长回文子串、长度和位置
*/
public static PalindromeResult longestPalindromeWithInfo(String s) {
if (s == null || s.length() == 0) {
return new PalindromeResult("", 0, 0, 0);
}
char[] T = preprocess(s);
int n = T.length;
int[] P = new int[n];
int center = 0;
int 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[i + P[i] + 1] == T[i - P[i] - 1]) {
P[i]++;
}
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
// 找到最大回文半径及其中心
int maxRadius = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxRadius) {
maxRadius = P[i];
centerIndex = i;
}
}
// 计算原始字符串中的位置
int start = (centerIndex - maxRadius) / 2;
String palindrome = s.substring(start, start + maxRadius);
return new PalindromeResult(palindrome, maxRadius, start, start + maxRadius - 1);
}
/**
* 结果封装类
*/
public static class PalindromeResult {
private String palindrome; // 回文子串
private int length; // 长度
private int start; // 起始索引
private int end; // 结束索引
public PalindromeResult(String palindrome, int length, int start, int end) {
this.palindrome = palindrome;
this.length = length;
this.start = start;
this.end = end;
}
// Getters
public String getPalindrome() { return palindrome; }
public int getLength() { return length; }
public int getStart() { return start; }
public int getEnd() { return end; }
@Override
public String toString() {
return String.format("回文串: '%s', 长度: %d, 位置: [%d, %d]",
palindrome, length, start, end);
}
}
/**
* 方法三：返回所有回文子串（可选）
*/
public static List<String> findAllPalindromes(String s) {
List<String> result = new ArrayList<>();
if (s == null || s.length() == 0) {
return result;
}
char[] T = preprocess(s);
int n = T.length;
int[] P = new int[n];
int center = 0;
int 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[i + P[i] + 1] == T[i - P[i] - 1]) {
P[i]++;
}
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
// 收集所有回文子串（长度大于1）
for (int i = 1; i < n - 1; i++) {
if (P[i] > 0) {
int start = (i - P[i]) / 2;
int end = start + P[i];
result.add(s.substring(start, end));
}
}
return result;
}
/**
* 测试方法
*/
public static void main(String[] args) {
// 测试用例
String[] testCases = {
"babad",
"cbbd",
"a",
"ac",
"racecar",
"abcba",
"aaaa",
"abacdfgdcaba"
};
System.out.println("Manacher算法测试结果：");
System.out.println("=" .repeat(50));
for (String test : testCases) {
String result = longestPalindrome(test);
PalindromeResult info = longestPalindromeWithInfo(test);
System.out.println("输入: \"" + test + "\"");
System.out.println("最长回文: \"" + result + "\"");
System.out.println("详细信息: " + info);
System.out.println("-".repeat(50));
}
// 测试查找所有回文子串
System.out.println("\n查找所有回文子串测试：");
String testStr = "ababa";
List<String> allPalindromes = findAllPalindromes(testStr);
System.out.println("字符串: \"" + testStr + "\"");
System.out.println("所有回文子串: " + allPalindromes);
// 性能测试
System.out.println("\n性能测试：");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1000000; i++) {
sb.append('a');
}
String longStr = sb.toString();
long startTime = System.currentTimeMillis();
String longResult = longestPalindrome(longStr);
long endTime = System.currentTimeMillis();
System.out.println("处理100万长度字符串用时: " + (endTime - startTime) + "ms");
System.out.println("最长回文长度: " + longResult.length());
}
}
2. 简化版本（仅核心功能）
public class ManacherSimple {
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
// 预处理
char[] T = new char[s.length() * 2 + 3];
T[0] = '^';
T[T.length - 1] = '$';
for (int i = 0; i < s.length(); i++) {
T[2 * i + 1] = '#';
T[2 * i + 2] = s.charAt(i);
}
T[T.length - 2] = '#';
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[i + P[i] + 1] == T[i - P[i] - 1]) {
P[i]++;
}
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
// 找到最大值
int maxLen = 0;
int centerIndex = 0;
for (int i = 0; i < n; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2;
return s.substring(start, start + maxLen);
}
public static void main(String[] args) {
System.out.println(longestPalindrome("babad")); // 输出: bab 或 aba
System.out.println(longestPalindrome("cbbd")); // 输出: bb
System.out.println(longestPalindrome("a")); // 输出: a
}
}
3. 逐步解析
关键步骤说明：
步骤1：预处理
// 原始: "aba"
// 预处理后: ^#a#b#a#$
// 索引: 0 1 2 3 4 5 6 7 8
// 字符: ^ # a # b # a # $
步骤2：计算回文半径数组 P[i]
P[i]表示以T[i]为中心的回文半径（包含中心）- 例如：
T = ^#a#b#a#$,P[4]=3（对应原始字符串的 “aba”）
步骤3：利用对称性
// 当 i < right 时，可以利用已知信息
int mirror = 2 * center - i; // i 关于 center 的对称点
P[i] = Math.min(right - i, P[mirror]);
步骤4：中心扩展
// 在已知半径基础上继续扩展
while (T[i + P[i] + 1] == T[i - P[i] - 1]) {
P[i]++;
}
步骤5：更新最右回文
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
4. 测试结果示例
输入: "babad"
最长回文: "bab" // 或 "aba"
详细信息: 回文串: 'bab', 长度: 3, 位置: [0, 2]
输入: "cbbd"
最长回文: "bb"
详细信息: 回文串: 'bb', 长度: 2, 位置: [1, 2]
输入: "racecar"
最长回文: "racecar"
详细信息: 回文串: 'racecar', 长度: 7, 位置: [0, 6]
5. 复杂度分析
-
时间复杂度：O(n)
- 虽然有两层循环，但内层扩展只会增加
right right从 0 增加到 n，总扩展次数 O(n)
- 虽然有两层循环，但内层扩展只会增加
-
空间复杂度：O(n)
- 需要存储预处理字符串和半径数组
6. 使用建议
- 处理超长字符串：Manacher 算法非常适合处理长字符串（百万级长度）
- 多次查询：如果需要对同一字符串多次查询不同位置的回文，可以缓存 P[] 数组
- 变体应用：可用于统计所有回文子串数量、判断任意子串是否为回文等
这个 Java 实现完整、高效且易于理解，可以直接在项目中使用！
这里是“一人公司”的成长家园。我们提供从产品曝光、技术变现到法律财税的全栈内容，并连接云服务、办公空间等稀缺资源，助你专注创造，无忧运营。
更多推荐
7
0- 0
已为社区贡献58条内容
所有评论(0)