Java 中查找回文子串的几种方法

1. 概述

在本篇文章中，我们将介绍几种在给定字符串中找出所有回文子串的方法，并分析每种方法的时间复杂度。

2. 暴力遍历法

暴力法是最直观的解法：我们遍历字符串的所有子串，并逐一判断每个子串是否是回文。

public Set<String> findAllPalindromesUsingBruteForceApproach(String input) {
    Set<String> palindromes = new HashSet<>();
    for (int i = 0; i < input.length(); i++) {
        for (int j = i + 1; j <= input.length(); j++) {
            if (isPalindrome(input.substring(i, j))) {
                palindromes.add(input.substring(i, j));
            }
        }
    }
    return palindromes;
}

其中，判断是否为回文的方法如下：

private boolean isPalindrome(String input) {
    StringBuilder plain = new StringBuilder(input);
    StringBuilder reverse = plain.reverse();
    return (reverse.toString()).equals(input);
}

当然，判断回文还有其他更高效的方法可以选用。

✅ 时间复杂度：O(n³)
❌ 对于大文本来说性能堪忧，不推荐用于高频或大数据量场景。

3. 中心扩展法

中心扩展法的核心思想是：将每个字符（或两个字符之间）作为回文的中心，向两边扩展，从而找出所有回文子串。

public Set<String> findAllPalindromesUsingCenter(String input) {
    Set<String> palindromes = new HashSet<>();
    for (int i = 0; i < input.length(); i++) {
        palindromes.addAll(findPalindromes(input, i, i + 1)); // 偶数长度
        palindromes.addAll(findPalindromes(input, i, i));     // 奇数长度
    }
    return palindromes;
}

具体扩展逻辑如下：

private Set<String> findPalindromes(String input, int low, int high) {
    Set<String> result = new HashSet<>();
    while (low >= 0 && high < input.length() && input.charAt(low) == input.charAt(high)) {
        result.add(input.substring(low, high + 1));
        low--;
        high++;
    }
    return result;
}

✅ 时间复杂度：O(n²)
⚠️ 相比暴力法已经优化不少，适合中等规模数据处理。

4. Manacher 算法

Manacher 算法可以在线性时间复杂度内找出最长回文子串。我们也可以用它来找出所有的回文子串。

4.1 初始化处理

首先，我们在字符串首尾加上特殊字符（如 @ 和 #），便于统一处理奇偶长度回文：

String formattedInput = "@" + input + "#";
char inputCharArr[] = formattedInput.toCharArray();

接着，定义一个二维数组 radius，分别记录奇数和偶数长度的回文半径：

int radius[][] = new int[2][input.length() + 1];

4.2 核心逻辑

遍历字符串，填充 radius 数组：

Set<String> palindromes = new HashSet<>();
int max;
for (int j = 0; j <= 1; j++) {
    radius[j][0] = max = 0;
    int i = 1;
    while (i <= input.length()) {
        palindromes.add(Character.toString(inputCharArr[i]));
        while (inputCharArr[i - max - 1] == inputCharArr[i + j + max])
            max++;
        radius[j][i] = max;
        int k = 1;
        while ((radius[j][i - k] != max - k) && (k < max)) {
            radius[j][i + k] = Math.min(radius[j][i - k], max - k);
            k++;
        }
        max = Math.max(max - k, 0);
        i += k;
    }
}

4.3 提取所有回文子串

最后，通过 radius 数组提取所有回文子串：

for (int i = 1; i <= input.length(); i++) {
    for (int j = 0; j <= 1; j++) {
        for (max = radius[j][i]; max > 0; max--) {
            palindromes.add(input.substring(i - max - 1, max + j + i - 1));
        }
    }
}

✅ **时间复杂度：O(n)**（理论上）
⚠️ 但实际提取所有回文子串时，由于 substring() 每次都创建新字符串，整体复杂度会退化为 **O(n²)**。这一点与低效的字符串拼接类似。

5. 总结

本文介绍了三种查找回文子串的方法：

方法	时间复杂度	是否推荐
暴力法	O(n³)	❌
中心扩展法	O(n²)	✅
Manacher 算法	O(n) 理论上	⚠️ 实际应用需注意性能陷阱

所有示例代码均可在 GitHub 获取。

Persistence

REST

Security