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;
    }
}

这个方法首先遍历字符串的每个字符，然后以该字符为中心向两边扩展，查找奇数长度的回文子串。接着，以当前字符及其右侧字符为中心向两边扩展，查找偶数长度的回文子串。在扩展过程中，我们使用哈希表存储已经找到的回文子串，以避免重复添加。

注意：这个方法可能会产生大量的哈希冲突，因此在实际应用中可能需要进一步优化哈希函数或使用其他数据结构来存储回文子串。