Java 数据结构与算法系列精讲之字符串暴力匹配

1. 基本概念

字符串匹配是一种非常常见的算法问题。给定一个字符串 A 和一个模式串 B，要求在字符串 A 中查找是否有 B 出现的位置，如果有，则返回第一次出现的位置，否则返回-1。字符串暴力匹配就是一种解决此问题的算法，它的基本思路就是从字符串 A 中从头开始一个字符一个字符地去匹配模式串 B 的每个字符，直到匹配完整个模式串。

2. 算法实现

字符串 A 的长度为n，模式串 B 的长度为m，时间复杂度为 O(nm)。

下面是字符串暴力匹配算法的实现代码：

public static int findFirstMatch(String A, String B) {
    int n = A.length();
    int m = B.length();
    for(int i = 0; i <= n-m; i++) { // 外层循环遍历 A 字符串
        int j = 0; // 内层循环遍历模式串 B
        for(j = 0; j < m; j++) {
            if(A.charAt(i+j) != B.charAt(j)) { // 找到第一个不匹配的字符
                break;
            }
        }
        if(j == m) { // 如果内循环完全执行完了，说明匹配到了模式串 B
            return i;
        }
    }
    return -1; // 没有找到匹配的子串
}

3. 算法分析

和其他字符串匹配算法比较，字符串暴力匹配算法实现简单，但是它的时间复杂度比较高，特别是在字符串 A 和模式串 B 的长度比较大时，它的效率会很低。对于一些场景，我们可能需要选择其他算法，例如 KMP 算法、Boyer-Moore 算法等。

下面是两个示例：

• 示例1：在字符串 A 中查找模式串 B “abcdea” 的第一次出现位置。

String A = "abczabcdea";
String B = "abcdea";
int index = findFirstMatch(A, B);
System.out.println(index); //输出：4

• 示例2：在字符串 A 中查找模式串 B “def” 的第一次出现位置。

String A = "abczabcdefg";
String B = "def";
int index = findFirstMatch(A, B);
System.out.println(index); //输出：-1

以上就是字符串暴力匹配算法的完整攻略，希望对您有所帮助！