Java实现字符串匹配的几种方法

字符串匹配是在给定文本中查找特定子串出现的位置的过程。在Java中，我们可以使用多种方法来实现字符串匹配。以下是几种常见的字符串匹配算法：

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

暴力匹配算法是一种简单的字符串匹配方法，其基本思想是从主串的第一个字符开始，逐个与模式串的字符进行比较，如果某个字符不相等，则比较失败，将主串的下一个字符与模式串的第一个字符重新开始比较；如果所有字符都相等，则匹配成功。

以下是使用Java实现暴力匹配算法的示例代码：

public static int[] bruteForce(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] result = new int[m]; // 存储匹配结果
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (text.charAt(i + j) != pattern.charAt(j)) { // 如果发现不匹配的字符
                result[j] = -1; // 将结果标记为-1，表示失败
                break; // 跳出内层循环
            } else {
                result[j] = i; // 记录匹配的位置
            }
        }
        if (Arrays.equals(result, new int[m])) { // 如果所有字符都匹配成功
            return result; // 返回匹配结果
        }
    }
    return null; // 如果没有找到匹配结果，则返回null
}

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

KMP算法是一种改进的字符串匹配算法，其基本思想是利用已经匹配过的部分信息，通过构建一个部分匹配表（也称为部分匹配数组），来指导后续的匹配过程。当匹配失败时，算法能够跳过一些不必要的比较，从而提高匹配效率。

以下是使用Java实现KMP算法的示例代码：

```java
public static int[] KMP(String text, String pattern) {
int[] lps = buildLPSArray(pattern); // 构建部分匹配表
int n = text.length();
int m = pattern.length();
int[] result = new int[m]; // 存储匹配结果
int i = 0, j = 0; // i和j分别表示主串和模式串的指针
while (i < n) {
if (text.charAt(i) == pattern.charAt(j)) { // 如果当前字符相等
i++; // 主串指针后移一位
j++; // 模式串指针后移一位
} else { // 如果当前字符不相等
if (j == 0 || (i - j + 1) < m) { // 如果模式串指针为0或者还有剩余未匹配的字符，则继续向前比较下一个字符
i++; // 主串指针后移一位
} else { // 如果已经没有剩余未匹配的字符，则将模式串指针回退一位，重新开始比较下一个字符
j = lps[j - 1]; // 回退模式串指针，重新开始比较下一个字符的位置由部分匹配表决定
}
}
if (j == m) { // 如果模式串已经全部匹配成功，则记录匹配位置并回退模式串指针（可选）
result[j - 1] = i - j; // 记录匹配位置（从0开始计数）
j = lps[j - 1]; // 回退模式串指针（可选）
} else if (i < n && text.charAt(i) == pattern.charAt(j)) { // 如果还有剩余未匹配的字符且当前字符相等，则继续向后比较下一个字符（可选）
i++; // 主串指针后移一位（可选）
j++; // 模式串指针后移一位（可选）
} else if (i < n && j > 0 && lps[j - 1] > i - j) { // 如果还有剩余未匹配的字符且当前字符不相等，则将模式串指针回退一位并重新开始比较下一个字符的位置由部分匹配表决定（可选）
j = lps[