本页面将简述字符串匹配问题以及它的解法．

## 字符串匹配问题

### 定义

又称模式匹配（pattern matching）．该问题可以概括为「给定字符串 $S$ 和 $T$，在主串 $S$ 中寻找子串 $T$」．字符 $T$ 称为模式串 (pattern)．

### 类型

-   单串匹配：给定一个模式串和一个待匹配串，找出前者在后者中的所有位置．
-   多串匹配：给定多个模式串和一个待匹配串，找出这些模式串在后者中的所有位置．
    -   出现多个待匹配串时，将它们直接连起来便可作为一个待匹配串处理．
    -   可以直接当做单串匹配，但是效率不够高．
-   其他类型：例如匹配一个串的任意后缀，匹配多个串的任意后缀……

## 暴力做法

简称 BF (Brute Force) 算法．该算法的基本思想是从主串 $S$ 的第一个字符开始和模式串 $T$ 的第一个字符进行比较，若相等，则继续比较二者的后续字符；否则，模式串 $T$ 回退到第一个字符，重新和主串 $S$ 的第二个字符进行比较．如此往复，直到 $S$ 或 $T$ 中所有字符比较完毕．

### 实现

=== "C++"
    ```cpp
    /*
     * s：待匹配的主串
     * t：模式串
     * n：主串的长度
     * m：模式串的长度
     */
    std::vector<int> match(char *s, char *t, int n, int m) {
      std::vector<int> ans;
      int i, j;
      for (i = 0; i < n - m + 1; i++) {
        for (j = 0; j < m; j++) {
          if (s[i + j] != t[j]) break;
        }
        if (j == m) ans.push_back(i);
      }
      return ans;
    }
    ```

=== "Python"
    ```python
    def match(s, t, n, m):
        if m < 1:
            return []
    
        ans = []
        for i in range(0, n - m + 1):
            for j in range(0, m):
                if s[i + j] != t[j]:
                    break
            else:
                ans.append(i)
        return ans
    ```

### 时间复杂度

设 $n$ 为主串的长度，$m$ 为模式串的长度．默认 $m\ll n$．

BF 算法匹配成功时，在最好情况下，只有一趟匹配成功，此趟比较次数为 $m$，而其余每趟不成功的匹配都发生在模式串的第一个字符，还需要 $n-m$ 次比较，总比较次数为 $n$，故时间复杂度为 $O(n)$；在最坏情况下，匹配成功的趟数为 $n-m+1$，每趟比较次数为 $m$，总比较次数为 $m(n-m+1)$，故时间复杂度为 $O(mn)$．

BF 算法匹配失败时，在最好情况下，每趟不成功的匹配都发生在模式串的第一个字符，BF 算法要执行 $n-m+1$ 次比较，时间复杂度为 $O(n)$；在最坏情况下，每趟不成功的匹配都发生在模式串的最后一个字符，BF 算法要执行 $m(n-m+1)$ 次比较，时间复杂度为 $O(mn)$．

如果模式串有至少两个不同的字符，则 BF 算法的平均时间复杂度为 $O(n)$．但是在 OI 题目中，给出的字符串一般都不是纯随机的．

## Hash 的方法

参见：[字符串哈希](./hash.md)

## KMP 算法

参见：[前缀函数与 KMP 算法](./kmp.md)
