Java實現基于哈希表的快速回文子串查找

在Java中，我們可以使用哈希表來優化快速回文子串查找。以下是一個使用哈希表實現的Java方法，用于查找給定字符串中所有回文子串：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PalindromeSubstringFinder {

    public static void main(String[] args) {
        String input = "babad";
        List<String> palindromes = findAllPalindromes(input);
        System.out.println("All palindrome substrings of \"" + input + "\": " + palindromes);
    }

    public static List<String> findAllPalindromes(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return result;
        }

        Map<Integer, String> map = new HashMap<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            // Odd length palindromes
            expandAroundCenter(s, i, i, map, result);
            // Even length palindromes
            expandAroundCenter(s, i, i + 1, map, result);
        }

        return result;
    }

    private static void expandAroundCenter(String s, int left, int right, Map<Integer, String> map, List<String> result) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            int hash = getHash(s, left, right);
            if (!map.containsKey(hash) || map.get(hash).length() == 0) {
                map.put(hash, s.substring(left, right + 1));
                result.add(s.substring(left, right + 1));
            }
            left--;
            right++;
        }
    }

    private static int getHash(String s, int left, int right) {
        int base = 131;
        int hash = 0;
        for (int i = left; i <= right; i++) {
            hash = hash * base + s.charAt(i);
        }
        return hash;
    }
}

這個方法首先遍歷字符串的每個字符，然后以該字符為中心向兩邊擴展，查找奇數長度的回文子串。接著，以當前字符及其右側字符為中心向兩邊擴展，查找偶數長度的回文子串。在擴展過程中，我們使用哈希表存儲已經找到的回文子串，以避免重復添加。

注意：這個方法可能會產生大量的哈希沖突，因此在實際應用中可能需要進一步優化哈希函數或使用其他數據結構來存儲回文子串。