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

在Java中，要快速定位回文子串，可以使用Manacher算法。這是一種線性時間復雜度的算法，可以在O(n)時間內找到字符串中的所有回文子串。以下是使用Manacher算法的基本步驟：

1. 預處理字符串：為了統(tǒng)一處理奇數長度和偶數長度的回文子串，我們需要在原始字符串的每個字符之間插入一個特殊字符（如’#‘），并在字符串的開頭和結尾添加特殊字符（如’%‘和’&'）。這樣，所有的回文子串都會被轉換為奇數長度。

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. 初始化輔助數組：創(chuàng)建一個數組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]