朴素模式匹配

模式匹配问题

字符串模式匹配是在主串 S 中寻找与模式串 T 相同的子串，并返回第一次出现的位置。若不存在，返回 0。

注意：

  • 子串是主串的一部分，一定存在于主串中。
  • 模式串不一定能在主串中找到。
  • 若主串长度为 n，模式串长度为 m，最多需要尝试 n - m + 1 个起始位置。

基本思想

朴素算法把主串中每个长度为 m 的候选子串依次与模式串比较：

  1. 先比较 S[1..m] 和 T[1..m]。
  2. 失配则比较 S[2..m+1] 和 T[1..m]。
  3. 继续右移，直到完全匹配或所有候选位置失败。

这种做法没有利用已经匹配过的信息；一旦失配，主串指针会回退到下一轮候选起点。

直接数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Index(SString s, SString t) {
    int i = 1;
    int j = 1;

    while (i <= s.length && j <= t.length) {
        if (s.ch[i] == t.ch[j]) {
            ++i;
            ++j;
        } else {
            i = i - j + 2;  // 回到本轮起点的下一个位置
            j = 1;          // 模式串从头开始
        }
    }

    if (j > t.length) {
        return i - t.length;
    }
    return 0;
}

关键是失配时的 i = i - j + 2：

  • 当前已经比较到 S[i] 和 T[j]。
  • 本轮候选起点是 i - j + 1。
  • 下一轮候选起点是 i - j + 2。

复杂度

设主串长度为 n，模式串长度为 m：

  • 最好情况：每个候选位置第一个字符就失配，约为 $O(n)$。
  • 最坏情况：每个候选位置都比较到最后才失配，约为 $O(nm)$。

朴素算法的缺陷是重复比较。KMP 的核心就是让主串指针不回退，只调整模式串指针。