字符串匹配

字符串匹配问题

单串匹配

一个模式串 (pattern)，一个待匹配串，找出前者在后者中的所有出现位置

多串匹配

多个模式串，一个待匹配串（多个待匹配串可以直接连起来）。

直接当做单串匹配肯定是可以的，但是效率不够高。

其他类型的字符串匹配问题

例如匹配一个串的任意后缀、匹配多个串的任意后缀等。

暴力做法

对于每个位置，尝试对模式串和待匹配串进行比对。

参考代码：

（伪代码）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
std::vector<int> match(char *a, char *b, int n, int m) {
  std::vector<int> ans;
  for (i = 0; i < n - m + 1; i++) {
    for (j = 0; j < m; j++) {
      if (a[i + j] != b[j]) break;
    }
    if (j == m) ans.push_back(i);
  }
  return ans;
}

时间复杂度分析：

最坏时间复杂度是 O(nm) 的，

最好是 O(n) 的。

如果字符集的大小大于 1（有至少两个不同的字符），平均时间复杂度是 O(n) 的。但是在 OI 题目中，给出的字符串一般都不是纯随机的。

Hash 的方法

参见 Hash

KMP 算法

参见 KMP

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论