2020-2021:teams:legal_string:字符串匹配_lgwza
|
2020-2021:teams:legal_string:字符串匹配_lgwza [2020/07/15 18:43] lgwza 创建 |
2020-2021:teams:legal_string:字符串匹配_lgwza [2020/07/15 18:44] (当前版本) lgwza |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | # 字符串匹配 | + | ====== 字符串匹配 ====== |
| + | ===== 字符串匹配问题 ===== | ||
| - | + | ==== 单串匹配 ==== | |
| - | ## 字符串匹配问题 | + | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | ### 单串匹配 | + | |
| 一个模式串(pattern)，一个待匹配串，找出前者在后者中的所有出现位置。 | 一个模式串(pattern)，一个待匹配串，找出前者在后者中的所有出现位置。 | ||
| - | + | ==== 多串匹配 ==== | |
| - | + | ||
| - | ### 多串匹配 | + | |
| 多个模式串，一个待匹配串（多个待匹配串可以直接连起来）。 | 多个模式串，一个待匹配串（多个待匹配串可以直接连起来）。 | ||
| 行 19: | 行 13: | ||
| 直接当作单串匹配肯定是可以的，但是效率不够高。 | 直接当作单串匹配肯定是可以的，但是效率不够高。 | ||
| + | ==== 匹配一个串的任意后缀 ==== | ||
| + | ==== 匹配多个串的任意后缀 ==== | ||
| - | ### 匹配一个串的任意后缀 | + | ===== 暴力做法 ===== |
| - | + | ||
| - | + | ||
| - | + | ||
| - | ### 匹配多个串的任意后缀 | + | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | ## 暴力做法 | + | |
| 对于每个位置，尝试对模式串和待匹配串进行比对。 | 对于每个位置，尝试对模式串和待匹配串进行比对。 | ||
| 行 37: | 行 25: | ||
| （伪代码） | （伪代码） | ||
| - | ```c++ | + | <code cpp> |
| std::vector<int> match(char *a, char *b, int n, int m) { | std::vector<int> match(char *a, char *b, int n, int m) { | ||
| std::vector<int> ans; | std::vector<int> ans; | ||
| 行 48: | 行 36: | ||
| return ans; | return ans; | ||
| } | } | ||
| - | ``` | + | </code> |
| 时间复杂度分析： | 时间复杂度分析： | ||
| 行 58: | 行 45: | ||
| 如果字符集的大小大于 1 （有至少两个不同的字符），平均时间复杂度是 $O(n)$ 的。但是在 OI 题目中，给出的字符串一般都不是纯随机的。 | 如果字符集的大小大于 1 （有至少两个不同的字符），平均时间复杂度是 $O(n)$ 的。但是在 OI 题目中，给出的字符串一般都不是纯随机的。 | ||
| + | ===== Hash 的方法 ===== | ||
| + | ===== KMP 算法 ===== | ||
| - | ## Hash 的方法 | + | ===== 参考链接 ===== |
| - | + | ||
| - | + | ||
| - | + | ||
| - | ## KMP 算法 | + | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | ## 参考链接 | + | |
| - | [Oi Wiki](https://oi-wiki.org/string/match/) | + | [[https://oi-wiki.org/string/match/|Oi Wiki]] |
2020-2021/teams/legal_string/字符串匹配_lgwza.1594809821.txt.gz · 最后更改: 2020/07/15 18:43 由 lgwza
