Java實(shí)現(xiàn)基于哈希表的快速回文子串查找

在Java中，我們可以使用哈希表來(lái)優(yōu)化快速回文子串查找。以下是一個(gè)使用哈希表實(shí)現(xiàn)的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;
    }
}

這個(gè)方法首先遍歷字符串的每個(gè)字符，然后以該字符為中心向兩邊擴(kuò)展，查找奇數(shù)長(zhǎng)度的回文子串。接著，以當(dāng)前字符及其右側(cè)字符為中心向兩邊擴(kuò)展，查找偶數(shù)長(zhǎng)度的回文子串。在擴(kuò)展過程中，我們使用哈希表存儲(chǔ)已經(jīng)找到的回文子串，以避免重復(fù)添加。

注意：這個(gè)方法可能會(huì)產(chǎn)生大量的哈希沖突，因此在實(shí)際應(yīng)用中可能需要進(jìn)一步優(yōu)化哈希函數(shù)或使用其他數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)回文子串。