Java字符串搜索算法有哪些

Java中有多種字符串搜索算法，以下是一些常見的：

1. 暴力匹配算法（Brute Force）

• 原理：從主串的第一個字符開始，逐個比較子串和主串的對應部分。
• 時間復雜度：O(n*m)，其中n是主串長度，m是子串長度。

2. KMP算法（Knuth-Morris-Pratt）

• 原理：預處理子串，構建部分匹配表（也稱為前綴函數），利用該表跳過不必要的比較。
• 時間復雜度：O(n+m)。

3. Boyer-Moore算法

• 原理：從子串的末尾開始匹配，利用壞字符規則和好后綴規則來跳過更多的字符。
• 最壞情況時間復雜度：O(n*m)，但在實際應用中通常比KMP更快。
• 平均時間復雜度：O(n/m)。

4. Rabin-Karp算法

• 原理：使用哈希函數計算子串和主串中每個窗口的哈希值，通過比較哈希值來快速排除不匹配的情況。
• 時間復雜度：平均O(n+m)，最壞情況下O(n*m)。

5. Sunday算法

• 原理：從子串的末尾開始匹配，每次移動子串直到找到一個字符在主串中不存在，或者匹配成功。
• 時間復雜度：平均O(n/m)，最壞情況下O(n*m)。

6. Aho-Corasick算法

• 原理：構建一個有限狀態自動機（FSA），可以同時搜索多個模式串。
• 時間復雜度：預處理階段O(m)，搜索階段O(n)。

7. Trie樹（前綴樹）

• 原理：構建一個樹形結構，每個節點代表一個字符，路徑表示字符串。適用于多模式匹配。
• 時間復雜度：插入O(m)，搜索O(m)。

8. Suffix Array（后綴數組）

• 原理：將主串的所有后綴排序，然后通過二分查找來快速定位子串。
• 時間復雜度：構建O(n log n)，搜索O(m log n)。

9. Suffix Tree（后綴樹）

• 原理：一種壓縮的后綴數組，可以更高效地進行字符串搜索和模式匹配。
• 時間復雜度：構建O(n)，搜索O(m)。

10. Z算法

• 原理：計算主串中每個位置的最長公共前后綴長度，利用這些信息進行快速匹配。
• 時間復雜度：O(n)。

Java中的實現

Java標準庫提供了String.indexOf()方法，它內部使用了優化的算法（通常是Boyer-Moore或其變種）。如果你需要自定義實現，可以考慮上述算法之一。

例如，KMP算法的Java實現：

public class KMPAlgorithm {
    public static int kmpSearch(String text, String pattern) {
        int[] lps = computeLPSArray(pattern);
        int i = 0; // index for text
        int j = 0; // index for pattern
        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == pattern.length()) {
                return i - j; // pattern found
            } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1; // pattern not found
    }

    private static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0;
        int i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        System.out.println("Pattern found at index: " + kmpSearch(text, pattern));
    }
}

選擇合適的算法取決于具體的應用場景和性能需求。