子串查找与暴力匹配

学习目标

本节学习字符串匹配中的基础方法：暴力匹配。

字符串匹配要解决的问题是：给定一个主串和一个模式串，判断模式串是否出现在主串中，并找到它出现的位置。

主串和模式串

在字符串匹配中，通常有两个字符串：

主串：被查找的长字符串。
模式串：需要查找的短字符串。

例如：

主串:   data structure
模式串: struct

我们要判断 struct 是否出现在 data structure 中。如果出现，还要找到它开始的位置。

暴力匹配的基本思想

暴力匹配的思路很直接：尝试每一个可能的起点，然后逐个比较字符。

从主串的第 0 个位置开始尝试匹配模式串。
如果当前字符都匹配，就继续比较下一个字符。
如果某个字符不匹配，就放弃当前起点。
起点向后移动一位，重新从模式串开头比较。
如果某个起点能完整匹配模式串，就返回这个起点。
如果所有起点都尝试失败，就说明模式串不存在。

暴力匹配代码

下面实现一个返回首次匹配位置的函数。如果没有匹配，返回 -1。

int indexOf(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();

    if (m == 0) {
        return 0;
    }

    for (int i = 0; i <= n - m; i++) {
        int j = 0;

        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }

        if (j == m) {
            return i;
        }
    }

    return -1;
}

int indexOf(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();

    if (m == 0) {
        return 0;
    }

    for (int i = 0; i <= n - m; i++) {
        int j = 0;

        while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
            j++;
        }

        if (j == m) {
            return i;
        }
    }

    return -1;
}

def index_of(text, pattern):
    n = len(text)
    m = len(pattern)

    if m == 0:
        return 0

    for i in range(n - m + 1):
        j = 0

        while j < m and text[i + j] == pattern[j]:
            j += 1

        if j == m:
            return i

    return -1

int IndexOf(string text, string pattern)
{
    int n = text.Length;
    int m = pattern.Length;

    if (m == 0)
    {
        return 0;
    }

    for (int i = 0; i <= n - m; i++)
    {
        int j = 0;

        while (j < m && text[i + j] == pattern[j])
        {
            j++;
        }

        if (j == m)
        {
            return i;
        }
    }

    return -1;
}

这四段代码都遵循同一个流程：外层循环枚举主串起点，内层循环比较模式串字符。

暴力匹配的复杂度

设主串长度为 $n$ ，模式串长度为 $m$ 。

最坏情况下，外层可能尝试大约 $n - m + 1$ 个起点；每个起点又可能比较接近 $m$ 个字符。因此暴力匹配的最坏时间复杂度通常记为 $O(nm)$ 。

空间方面，暴力匹配只使用少量变量，因此额外空间复杂度通常是 $O(1)$ 。

暴力匹配的优点和缺点

暴力匹配的优点是简单直观，容易实现，适合帮助我们理解字符串匹配的基本问题。

它的缺点是遇到某些重复结构较多的字符串时，会进行大量重复比较。例如主串和模式串中有很多相同前缀时，每次失败后都从头开始比较，浪费了已经得到的信息。

KMP 算法正是为了解决这种重复比较问题而出现的。

本节小结

暴力匹配通过枚举主串中的每个可能起点，并逐字符比较模式串，来完成子串查找。

它容易理解，额外空间少，但最坏时间复杂度可能达到 $O(nm)$ 。后续学习 KMP 时，要重点理解它如何利用已经匹配过的信息减少重复比较。