WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
字符串部分简介
字符串基础
标准库
字符串匹配
字符串哈希
字典树 (Trie)
前缀函数与 KMP 算法
Boyer-Moore算法
Z 函数（扩展 KMP）
自动机
AC 自动机
后缀数组 (SA)
后缀自动机 (SAM)
广义后缀自动机
后缀树
Manacher
回文树
序列自动机
最小表示法
Lyndon 分解
20 objects
本站非官方，所收集资源均来源于网络。
字符串匹配 - 字符串
## 字符串匹配问题 ### 单串匹配 一个模式串 (pattern)，一个待匹配串，找出前者在后者中的所有出现位置 ### 多串匹配 多个模式串，一个待匹配串（多个待匹配串可以直接连起来）。 直接当做单串匹配肯定是可以的，但是效率不够高。 ### 其他类型的字符串匹配问题 例如匹配一个串的任意后缀、匹配多个串的任意后缀等。 ## 暴力做法 对于每个位置，尝试对模式串和待匹配串进行比对。 参考代码： （伪代码） ```cpp 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](#)
wiki(I:)
比赛相关
字符串部分简介
