跳转至

字符串匹配

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

字符串匹配问题

定义

又称模式匹配(pattern matching)。该问题可以概括为「给定字符串 ST,在主串 S 中寻找子串 T」。字符 T 称为模式串 (pattern)。

类型

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

暴力做法

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

实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/*
* 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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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 为模式串的长度。默认 mn

在最好情况下,BF 算法匹配成功时,时间复杂度为 O(n);匹配失败时,时间复杂度为 O(m)

在最坏情况下,每趟不成功的匹配都发生在模式串的最后一个字符,BF 算法要执行 m(nm+1) 次比较,时间复杂度为 O(nm)

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

Hash 的方法

参见:字符串哈希

KMP 算法

参见:前缀函数与 KMP 算法


0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn