Java中如何快速定位回文子串

在Java中，要快速定位回文子串，可以使用Manacher算法。这是一种线性时间复杂度的算法，可以在O(n)时间内找到字符串中的所有回文子串。以下是使用Manacher算法的基本步骤：

1. 预处理字符串：为了统一处理奇数长度和偶数长度的回文子串，我们需要在原始字符串的每个字符之间插入一个特殊字符（如’#‘），并在字符串的开头和结尾添加特殊字符（如’%‘和’&'）。这样，所有的回文子串都会被转换为奇数长度。

public static String preprocess(String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        sb.append('#').append(s.charAt(i));
    }
    sb.append('&');
    return sb.toString();
}

2. 初始化辅助数组：创建一个数组P，用于存储以每个字符为中心的回文子串的半径（包括中心字符）。

public static int[] manacher(String s) {
    String preprocessed = preprocess(s);
    int n = preprocessed.length();
    int[] P = new int[n];
    int center = 0, right = 0;

    for (int i = 0; i < n; i++) {
        if (i < right) {
            int mirror = 2 * center - i;
            P[i] = Math.min(right - i, P[mirror]);
        }

        int left = i - (P[i] + 1);
        int right = i + (P[i] + 1);

        while (left >= 0 && right < n && preprocessed.charAt(left) == preprocessed.charAt(right)) {
            P[i]++;
            left--;
            right++;
        }

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

    return P;
}

3. 查找回文子串：遍历辅助数组P，找到所有值为奇数的元素，它们对应的原始字符串中的字符就是回文子串的中心。根据中心向两边扩展，可以找到所有的回文子串。

public static List<String> findPalindromes(String s) {
    List<String> result = new ArrayList<>();
    int[] P = manacher(s);
    int n = s.length();

    for (int i = 0; i < n; i++) {
        if (P[i] % 2 == 1) {
            int center = i;
            int left = center - (P[i] / 2);
            int right = center + (P[i] / 2);
            result.add(s.substring(left, right + 1));
        }
    }

    return result;
}

现在，你可以使用findPalindromes方法在给定的字符串中查找所有的回文子串。例如：

public static void main(String[] args) {
    String s = "babad";
    List<String> palindromes = findPalindromes(s);
    System.out.println("Palindromes in \"" + s + "\": " + palindromes);
}

输出：

Palindromes in "babad": [baba, bab, a]