字符串匹配
字符串匹配问题¶
单串匹配¶
一个模式串 (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;
}
|
时间复杂度分析:
最坏时间复杂度是
最好是
如果字符集的大小大于 1(有至少两个不同的字符),平均时间复杂度是
Hash 的方法¶
参见 Hash
KMP 算法¶
参见 KMP
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用