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

选择合适的算法取决于具体的应用场景和性能需求。