07-字符串匹配算法

实现一个字符串匹配算法，并分析其时间复杂度和空间复杂度。

public class StringMatcher {
    public static int naiveStringSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        for (int i = 0; i < n - m + 1; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }
}

使用朴素的暴力搜索算法。这种算法的思想是比较模式串和文本串中每个可能的位置是否匹配，直到匹配成功或者遍历完所有位置。

该算法的时间复杂度为O(nm)，其中 n 是文本串的长度，m 是模式串的长度。由于在最坏情况下，需要比较所有可能的位置才能找到匹配项，所以该算法的时间复杂度是相对比较高的。

空间复杂度主要取决于字符串的长度，因此我们可以将其视为 O(n+m)。

如果需要更快速、更高效的字符串匹配算法，可以考虑使用基于哈希表或 KMP 算法等其他算法。

验证：

public static void main(String[] args) {
    String s = "helloworld";
    int low = StringMatcher.naiveStringSearch(s, "low");
    //3
    System.out.println("low = " + low);
}