快捷導(dǎo)航

Java回文字符串查找和計(jì)數(shù)實(shí)現(xiàn)方式

更新時間：2026年04月09日 10:45:10 作者：逆流的小魚168

文章簡要介紹了回文字符串的概念、性質(zhì)和應(yīng)用場景,然后詳細(xì)講解了幾種查找回文子字符串的方法（暴力方法、中心擴(kuò)展算法、Manacher算法）,以及使用哈希表統(tǒng)計(jì)回文子字符串出現(xiàn)次數(shù)的方法,并提供了Java代碼示例,最后,文章討論了優(yōu)化方案和性能分析

1. 回文字符串基礎(chǔ)知識

回文字符串是一系列字符，正著讀和反著讀都是一樣的，如“madam”或“racecar”。

在編程中，我們時常需要檢測或者處理回文字符串，例如數(shù)據(jù)驗(yàn)證、DNA序列分析等。

1.1 簡述回文字符串的定義

回文是指一個字符串忽略標(biāo)點(diǎn)、大小寫和空格，正向和反向都一樣。

回文字符串的定義很簡單，舉例來說：“level”, “deified”, “civic” 和 “radar” 等都是回文字符串。

1.2 回文字符串的性質(zhì)和應(yīng)用場景

性質(zhì)：回文字符串的主要性質(zhì)是它們是對稱的，其第一個字符和最后一個字符相同，第二個字符和倒數(shù)第二個字符相同，以此類推。
應(yīng)用場景：回文字符串的概念在許多領(lǐng)域都有應(yīng)用，例如文本編輯器中查找回文單詞，生物學(xué)中查找特定的DNA序列，甚至在某些加密算法中也會使用到回文結(jié)構(gòu)。

2. 查找回文子字符串的方法

2.1. 暴力方法

暴力方法是通過檢查所有的子字符串，來確定它們是否為回文。以下是使用Java語言的代碼示例：

public class BruteForcePalindrome {

    public static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    public static void findPalindromes(String input) {
        int n = input.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                String substr = input.substring(i, j);
                if (isPalindrome(substr)) {
                    System.out.println(substr);
                }
            }
        }
    }

    public static void main(String[] args) {
        String s = "ababa";
        findPalindromes(s);
    }
}

2.2. 中心擴(kuò)展算法

中心擴(kuò)展算法從每個可能的中心開始檢查可能的最長回文。

以下是Java代碼示例：

public class CenterExpansionPalindrome {

    public static void findPalindromes(String input) {
        for (int center = 0; center < 2 * input.length() - 1; center++) {
            int left = center / 2;
            int right = left + center % 2;
            while (left >= 0 && right < input.length() && input.charAt(left) == input.charAt(right)) {
                System.out.println(input.substring(left, right + 1));
                left--;
                right++;
            }
        }
    }

    public static void main(String[] args) {
        String s = "racecar";
        findPalindromes(s);
    }
}

2.3. Manacher’s Algorithm(馬拉車算法)

馬拉車算法是一種高效的查找最長回文子字符串的方法。

這里是一個Java實(shí)現(xiàn)：

public class ManacherAlgorithm {

    private static String preProcess(String s) {
        StringBuilder sb = new StringBuilder("$#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            sb.append('#');
        }
        sb.append('@');
        return sb.toString();
    }

    public static void findPalindromes(String input) {
        String T = preProcess(input);
        int n = T.length();
        int[] P = new int[n];
        int C = 0, R = 0;
        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * C - i;
            P[i] = (R > i) ? Math.min(R - i, P[i_mirror]) : 0;
            while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
                P[i]++;
            }
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
        }
        for (int i = 1; i < n - 1; i++) {
            if(P[i] > 0) {
                System.out.println(input.substring((i - 1 - P[i]) / 2, (i - 1 + P[i]) / 2));
            }
        }
    }

    public static void main(String[] args) {
        String s = "abababa";
        findPalindromes(s);
    }
}

在上述實(shí)現(xiàn)中，先對原始字符串進(jìn)行預(yù)處理，在每個字符間插入特殊符號（比如#），這樣可以統(tǒng)一處理偶數(shù)長度和奇數(shù)長度的回文。然后使用ManacherAlgorithm中的findPalindromes方法尋找回文子字符串。

3. 統(tǒng)計(jì)回文子字符串出現(xiàn)次數(shù)

3.1. 哈希表的使用

在找到所有回文子字符串后，我們需要統(tǒng)計(jì)它們的出現(xiàn)次數(shù)。要有效地做到這一點(diǎn)，我們可以使用哈希表（在Java中通常是HashMap）來存儲每個子字符串及其對應(yīng)的計(jì)數(shù)。

下面的Java代碼示例展示了如何使用哈希表來統(tǒng)計(jì)回文子字符串的次數(shù)。

import java.util.HashMap;
import java.util.Map;

public class PalindromeFrequency {

    public static Map<String, Integer> countPalindromes(String[] palindromes) {
        Map<String, Integer> palindromeCount = new HashMap<>();
        for (String palindrome : palindromes) {
            palindromeCount.put(palindrome, palindromeCount.getOrDefault(palindrome, 0) + 1);
        }
        return palindromeCount;
    }

    // 假設(shè)我們已經(jīng)有了一個回文子字符串?dāng)?shù)組
    public static void main(String[] args) {
        String[] palindromes = {"aba", "level", "ana", "level"};
        Map<String, Integer> count = countPalindromes(palindromes);
        for (String key : count.keySet()) {
            System.out.println("Palindrome: " + key + ", Count: " + count.get(key));
        }
    }
}

3.2. 結(jié)果去重和統(tǒng)計(jì)實(shí)現(xiàn)

為了去除重復(fù)的回文子字符串，我們可以在將字符串加入哈希表之前，先檢查它是否已經(jīng)存在。此外，我們也可能需要對回文字符串按照一定的規(guī)則（如字母表順序）進(jìn)行排序，以便更好地組織和查詢。

以下代碼示例展示了如果同時考慮去重和統(tǒng)計(jì)：

import java.util.TreeMap;

public class PalindromeFrequencyAndDeduplication {

    public static TreeMap<String, Integer> countPalindromes(String input) {
        TreeMap<String, Integer> palindromeCount = new TreeMap<>();
        // 此處省略查找回文子字符串的代碼... （可以使用上面討論的任何算法）
        // 假設(shè)我們已經(jīng)有了一個包含所有回文子字符串的列表
        String[] foundPalindromes = {"aba", "level", "ana", "level"};
        for (String palindrome : foundPalindromes) {
            palindromeCount.put(palindrome, palindromeCount.getOrDefault(palindrome, 0) + 1);
        }
        return palindromeCount;
    }

    public static void main(String[] args) {
        String s = "abacdclevelanalevel";
        TreeMap<String, Integer> count = countPalindromes(s);
        for (Map.Entry<String, Integer> entry : count.entrySet()) {
            System.out.println("Palindrome: " + entry.getKey() + ", Count: " + entry.getValue());
        }
    }
}

使用TreeMap而不是HashMap是因?yàn)門reeMap會根據(jù)鍵自然排序，使得輸出更易于閱讀和檢查。

4. 具體實(shí)現(xiàn)

4.1. 純Java實(shí)現(xiàn)代碼示例

現(xiàn)在來實(shí)現(xiàn)一個完整的Java類，該類可以一次性查找所有的回文子字符串，并統(tǒng)計(jì)每個回文子字符串的出現(xiàn)次數(shù)。

import java.util.HashMap;
import java.util.Map;

public class PalindromeFinder {

    private static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    public static Map<String, Integer> findAllPalindromes(String s) {
        Map<String, Integer> palindromeOccurrences = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String subStr = s.substring(i, j);
                if (isPalindrome(subStr)) {
                    palindromeOccurrences.put(subStr, palindromeOccurrences.getOrDefault(subStr, 0) + 1);
                }
            }
        }
        return palindromeOccurrences;
    }

    public static void main(String[] args) {
        String s = "abaxabaxabb";
        Map<String, Integer> palindromes = findAllPalindromes(s);
        for (Map.Entry<String, Integer> entry : palindromes.entrySet()) {
            System.out.println("Palindrome: " + entry.getKey() + ", Count: " + entry.getValue());
        }
    }
}

4.2. 優(yōu)化方案和性能分析

盡管上述實(shí)現(xiàn)可以工作，但在大型字符串上可能會變得非常慢。

優(yōu)化可以從兩個方面進(jìn)行：

使用更高效的算法，比如Manacher’s Algorithm，來找回文子串。
對記錄和統(tǒng)計(jì)過程進(jìn)行優(yōu)化，比如使用TreeMap以保持排序，或者其它結(jié)構(gòu)來優(yōu)化查詢和更新操作。

性能方面，我們應(yīng)該考慮算法的時間復(fù)雜度和空間復(fù)雜度。原始的暴力搜索算法的時間復(fù)雜度是O(n^3)，并且我們還需要額外的空間來存儲所有的子字符串和計(jì)數(shù)。優(yōu)化后的算法，如Manacher’s算法，將時間復(fù)雜度提高到了O(n)，這對于處理長字符串?dāng)?shù)據(jù)來說，提升是非常明顯的。