网站建设的目的是什么,如何建网站做传奇网友,婚庆网站建设方案,深圳手机端网站建设专业公司文章目录字符串基础字符串的存储标准库字符串匹配单串匹配多串匹配其他类型的字符串匹配问题字符串哈希Hash 的实现Hash 的分析与改进错误率多次询问子串哈希Hash 的应用字符串匹配允许 k次失配的字符串匹配最长回文子串最长公共子字符串确定字符串中不同子字符串的数量字典树 …
文章目录字符串基础字符串的存储标准库字符串匹配单串匹配多串匹配其他类型的字符串匹配问题字符串哈希Hash 的实现Hash 的分析与改进错误率多次询问子串哈希Hash 的应用字符串匹配允许 k次失配的字符串匹配最长回文子串最长公共子字符串确定字符串中不同子字符串的数量字典树 (Trie)应用检索字符串AC 自动机维护异或极值AC 自动机Manacher字符串基础 字符串的存储
使用 char 数组存储用空字符 \0 表示字符串的结尾。C 风格字符串使用 C 标准库提供的 string 类。字符串常量可以用字符串字面值用双引号括起来的字符串表示。
标准库
C 标准库是在对字符数组进行操作:char[]/const char*
代码作用strlen(const char *str)返回从 str[0] 开始直到 ‘\0’ 的字符数。注意未开启 O2 优化时该操作写在环条件中复杂度是 O(n)O(n)O(n)的。printf(%s, s)用 %s 来输出一个字符串字符数组。scanf(%s, s)用 %s 来读入一个字符串字符数组。sscanf(const char *__source, const char *__format, …)从字符串 __source 里读取变量比如 sscanf(str,%d,a)。sprintf(char *__stream, const char *__format, …)将 __format 字符串里的内容输出到 __stream 中比如 sprintf(str,%d,i)。strcmp(const char *str1, const char *str2)按照字典序比较 str1 str2 若 str1 字典序小返回负值两者一样返回 0str1 字典序更大则返回正值。请注意不要简单的认为返回值只有0 1-1 三种在不同平台下的返回值都遵循正负但并非都是 0-11。strcpy(char *str, const char *src)把 src 中的字符复制到 str 中str src 均为字符数组头指针返回值为 str 包含空终止符号 ‘\0’。strncpy(char *str, const char *src, int cnt)复制至多 cnt 个字符到 str 中若 src 终止而数量未达 cnt 则写入空字符到 str 直至写入总共 cnt 个字符。strcat(char *str1, const char *str2):将 str2 接到 str1 的结尾用 *str2 替换 str1 末尾的 ‘\0’ 返回 str1。strstr(char *str1, const char *str2)若 str2 是 str1 的子串则返回 str2 在 str1 的首次出现的地址如果 str2 不是 str1 的子串则返回 NULL。strchr(const char *str, int c)找到在字符串 str 中第一次出现字符 c 的位置并返回这个位置的地址。如果未找到该字符则返回 NULL。strrchr(const char *str, char c)找到在字符串 str 中最后一次出现字符 c 的位置并返回这个位置的地址。如果未找到该字符则返回 NULL。
C 标准库是在对字符串对象进行操作同时也提供对字符数组的兼容。 std::string
代码作用重载了赋值运算符 当 两边是 string/char/char[]/const char* 类型时可以将这两个变量连接返回连接后的字符串string。赋值运算符 右侧可以是 const string/string/const char*/char*。访问运算符 [cur]返回 cur 位置的引用。访问函数 data()/c_str()返回一个 const char* 指针内容与该 string 相同。容量函数 size()返回字符串字符个数。find(ch, start 0)查找并返回从 start 开始的字符 ch 的位置rfind(ch) 从末尾开始查找并返回第一个找到的字符 ch 的位置皆从 0开始如果查找不到返回 -1。substr(start, len)可以从字符串的 start从 0开始截取一个长度为 len 的字符串缺省 len 时代码截取到字符串末尾。append(s)将 s 添加到字符串末尾。append(s, pos, n)将字符串 s 中从 pos 开始的 n 个字符连接到当前字符串结尾。replace(pos, n, s)删除从 pos 开始的 n 个字符然后在 pos 处插入串 s。erase(pos, n)删除从 pos 开始的 n 个字符。insert(pos, s)在 pos 位置插入字符串 s。std::string重载了比较逻辑运算符复杂度是 O(n)的。
字符串匹配
单串匹配
一个模式串 (pattern)一个待匹配串找出前者在后者中的所有出现位置 举例Oulipo HDU - 1686哈希或KMP匹配字符串
多串匹配
多个模式串一个待匹配串多个待匹配串可以直接连起来。 直接当做单串匹配肯定是可以的但是效率不够高。 举例Keywords Search HDU - 2222AC自动机模板
其他类型的字符串匹配问题
例如匹配一个串的任意后缀、匹配多个串的任意后缀等。
字符串哈希
Hash 的核心思想在于将输入映射到一个值域较小、可以方便比较的范围。 Warning 这里的“值域较小”在不同情况下意义不同。 在 哈希表 中值域需要小到能够接受线性的空间与时间复杂度。 在字符串哈希中值域需要小到能够快速比较10910^9109、101810^{18}1018 都是可以快速比较的。 同时为了降低哈希冲突率值域也不能太小。 我们定义一个把字符串映射到整数的函数 fff这个fff 称为是 Hash 函数。 我们希望这个函数 fff 可以方便地帮我们判断两个字符串是否相等。 具体来说哈希函数最重要的性质可以概括为下面两条
在 Hash 函数值不一样的时候两个字符串一定不一样在 Hash 函数值一样的时候两个字符串不一定一样但有大概率一样且我们当然希望它们总是一样的。
Hash 函数值一样时原字符串却不一样的现象我们成为哈希碰撞。 我们需要关注的是什么 时间复杂度和 Hash 的准确率。 通常我们采用的是多项式 Hash 的方法对于一个长度为 lll 的字符串 s来说我们可以这样定义多项式 Hash 函数f(s)∑i1ls[i]×bl−i(modf(s)\sum^{l}_{i1}s[i]\times b^{l-i}(modf(s)∑i1ls[i]×bl−i(mod M)M)M)。例如对于字符串xyzxyzxyz 其哈希函数值为xb2ybzxb^2ybzxb2ybz 。 特别要说明的是也有很多人使用的是另一种 Hash 函数的定义即f(s)∑i1ls[i]×bi−1(modf(s)\sum^{l}_{i1}s[i]\times b^{i-1}(modf(s)∑i1ls[i]×bi−1(mod M)M)M) 这种定义下同样的字符串 xyzxyzxyz的哈希值就变为了 xbyzb2xbyzb^2xbyzb2 了。显然上面这两种哈希函数的定义函数都是可行的但二者在之后会讲到的计算子串哈希值时所用的计算式是不同的因此千万注意 不要弄混了这两种不同的 Hash 方式。由于前者的 Hash 定义计算更简便、使用人数更多、且可以类比为一个 b 进制数来帮助理解所以本文下面所将要讨论的都是使用 f(s)∑i1ls[i]×bl−i(modf(s)\sum^{l}_{i1}s[i]\times b^{l-i}(modf(s)∑i1ls[i]×bl−i(mod M)M)M) 来定义的 Hash 函数。
下面讲一下如何选择 M和计算哈希碰撞的概率。
这里 M 需要选择一个素数至少要比最大的字符要大b 可以任意选择。如果我们用未知数 x 替代b 那么f(x)f(x)f(x) 实际上是多项式环ZM[x]\mathbb{Z}_{M}[x]ZM[x] 上的一个多项式。考虑两个不同的字符串 st有f(s)f(t)f(s)f(t)f(s)f(t) 。我们记h(x)f(s)−f(t)∑i1l(s[i]−t[i])xl−i(modh(x)f(s)-f(t)\sum^{l}_{i1}(s[i]-t[i])x^{l-i}(modh(x)f(s)−f(t)∑i1l(s[i]−t[i])xl−i(mod M)M)M) 其中lmax(∣s∣,∣t∣)lmax(|s|,|t|)lmax(∣s∣,∣t∣) 。可以发现 h(x) 是一个 l−1l-1l−1 阶的非零多项式。如果 s与t 在xb 的情况下哈希碰撞则 b是h(x) 的一个根。由于 h(x) 在ZM\mathbb{Z}_{M}ZM 是一个域等价于 M 是一个素数这也是为什么 M 要选择素数的原因的时候最多有l−1l-1l−1 个根如果我们保证 b 是从 [0,M) 之间均匀随机选取的那么 f(s)f(s)f(s) 与 f(t)f(t)f(t) 碰撞的概率可以估计为 l−1M\frac{l-1}{M}Ml−1。简单验算一下可以发现如果两个字符串长度都是 1 的时候哈希碰撞的概率为 1−1M\frac{1-1}{M}M1−10此时不可能发生碰撞。
Hash 的实现
参考代码效率低下的版本实际使用时一般不会这么写
using std::string;const int M 1e9 7;
const int B 233;typedef long long ll;int get_hash(const string s) {int res 0;for (int i 0; i s.size(); i) {res (ll)(res * B s[i]) % M;}return res;
}bool cmp(const string s, const string t) {return get_hash(s) get_hash(t);
}Hash 的分析与改进
错误率
若进行 n次比较每次错误率 1M\frac{1}M{}M1那么总错误率是1−(1−1M)n1-(1-\frac{1}{M})^{n}1−(1−M1)n。在随机数据下若M1097M10^{9}7M1097 n106n10^6n106错误率约为 11000\frac{1}{1000}10001并不是能够完全忽略不计的。 所以进行字符串哈希时经常会对两个大质数分别取模这样的话哈希函数的值域就能扩大到两者之积错误率就非常小了。
多次询问子串哈希
单次计算一个字符串的哈希值复杂度是O(n) 其中 n为串长与暴力匹配没有区别如果需要多次询问一个字符串的子串的哈希值每次重新计算效率非常低下。 一般采取的方法是对整个字符串先预处理出每个前缀的哈希值将哈希值看成一个b 进制的数对M 取模的结果这样的话每次就能快速求出子串的哈希了
令fi(s)f_{i}(s)fi(s) 表示 f(s[1...i])f(s[1...i])f(s[1...i])即原串长度为 iii 的前缀的哈希值那么按照定义有 fi(s)s[1]×bi−1s[2]×bi−2...s[i−1]×bs[i]f_i(s)s[1]\times b^{i-1}s[2]\times b^{i-2}...s[i-1]\times bs[i]fi(s)s[1]×bi−1s[2]×bi−2...s[i−1]×bs[i]
现在我们想要用类似前缀和的方式快速求出f(s[l...r])f(s[l...r])f(s[l...r]) 按照定义有字符串 s[l...r]s[l...r]s[l...r]的哈希值为 f(s[l...r])s[l]×br−ls[l1]×br−l−1...s[r−l]×bs[r]f(s[l...r])s[l]\times b^{r-l}s[l1]\times b^{r-l-1}...s[r-l]\times bs[r]f(s[l...r])s[l]×br−ls[l1]×br−l−1...s[r−l]×bs[r]
对比观察上述两个式子我们发现 f(s[l...r])fr(s)−fl−1(s)×br−l1f(s[l...r])f_r(s)-f_{l-1}(s)\times b^{r-l1}f(s[l...r])fr(s)−fl−1(s)×br−l1 成立因此我们用这个式子就可以快速得到子串的哈希值。其中br−l1b^{r-l1}br−l1 可以O(n) 的预处理出来然后O(1) 的回答每次询问当然也可以快速幂 O(log n)的回答每次询问。
Hash 的应用
字符串匹配
求出模式串的哈希值后求出文本串每个长度为模式串长度的子串的哈希值分别与模式串的哈希值比较即可。
允许 k次失配的字符串匹配
问题给定长为 n 的源串 以及长度为m 的模式串 要求查找源串中有多少子串与模式串匹配。s′ss′ 与s 匹配当且仅当 s′ss′与s 长度相同且最多有 k 个位置字符不同。其中 1≤n,m≤1061\leq n,m\leq 10^61≤n,m≤1060≤k≤50\leq k\leq 50≤k≤5。
这道题无法使用 KMP 解决但是可以通过哈希 二分来解决。
枚举所有可能匹配的子串假设现在枚举的子串为s′ss′ 通过哈希 二分可以快速找到 s′ss′ 与p 第一个不同的位置。之后将 s′ss′ 与 p 在这个失配位置及之前的部分删除掉继续查找下一个失配位置。这样的过程最多发生 k 次。总的时间复杂度为O(mknO(mknO(mkn log2log_2log2 m)m)m) 。
最长回文子串
二分答案判断是否可行时枚举回文中心对称轴哈希判断两侧是否相等。需要分别预处理正着和倒着的哈希值。时间复杂度O(nO(nO(n logloglog n)n)n) 。 这个问题可以使用 manacher 算法 在 O(n)O(n)O(n) 的时间内解决。
通过哈希同样可以O(n)O(n)O(n) 解决这个问题具体方法就是记 RiR_{i}Ri 表示以 iii 作为结尾的最长回文的长度那么答案就是maxi1nRimax^{n}_{i1}R_{i}maxi1nRi 。考虑到 Ri≤Ri−12R_i\leq R_{i-1}2Ri≤Ri−12因此我们只需要暴力从 Ri−12R_{i-1}2Ri−12开始递减直到找到第一个回文即可。记变量 zzz 表示当前枚举的 RiR_iRi初始时为0 则 zzz 在每次 iii 增大的时候都会增大 2之后每次暴力循环都会减少1 故暴力循环最多发生2n 次总的时间复杂度为 O(n)。
最长公共子字符串
问题给定 m 个总长不超过n 的非空字符串查找所有字符串的最长公共子字符串如果有多个任意输出其中一个。其中1≤m,n≤1061\leq m,n\leq10^61≤m,n≤106 。
很显然如果存在长度为k 的最长公共子字符串那么 k-1 的公共子字符串也必定存在。因此我们可以二分最长公共子字符串的长度。假设现在的长度为k check(k) 的逻辑为我们将所有所有字符串的长度为k 的子串分别进行哈希将哈希值放入 n 个哈希表中存储。之后求交集即可。 时间复杂度为O(nO(nO(n log2log_2log2 nm)\frac{n}{m})mn) 。
确定字符串中不同子字符串的数量
问题给定长为n 的字符串仅由小写英文字母组成查找该字符串中不同子串的数量。
为了解决这个问题我们遍历了所有长度为 l1,...,nl1,...,nl1,...,n 的子串。对于每个长度为 lll我们将其 Hash 值乘以相同的 b 的幂次方并存入一个数组中。数组中不同元素的数量等于字符串中长度不同的子串的数量并此数字将添加到最终答案中。 为了方便起见我们将使用 h[i]h[i]h[i] 作为 Hash 的前缀字符并定义h[0]0h[0]0h[0]0 。
字典树 (Trie)
字典树英文名 trie。顾名思义就是一个像字典一样的树。 先放一张图 可以发现这棵字典树用边来代表字母而从根结点到树上某一结点的路径就代表了一个字符串。举个例子1→4→8→121\rightarrow4\rightarrow8\rightarrow121→4→8→12 表示的就是字符串 caa。
trie 的结构非常好懂我们用 δ(u,c)\delta(u,c)δ(u,c) 表示结点uuu 的 ccc 字符指向的下一个结点或着说是结点 uuu 代表的字符串后面添加一个字符 ccc 形成的字符串的结点。 ccc 的取值范围和字符集大小有关不一定是 000~26。
有时需要标记插入进 trie 的是哪些字符串每次插入完成时在这个字符串所代表的节点处打上标记即可。 Phone List POJ - 3630字典树模板题
应用
检索字符串
字典树最基础的应用——查找一个字符串是否在“字典”中出现过。 例题字典树模板洛谷P2580 于是他错误的点名开始了
AC 自动机
trie 是 AC 自动机 的一部分。
维护异或极值
将数的二进制表示看做一个字符串就可以建出字符集为{0,1} 的 trie 树。
前缀函数与 KMP 算法 Boyer-Moore算法 Z 函数扩展 KMP 自动机
AC 自动机
Keywords Search HDU - 2222AC自动机模板
后缀数组 (SA) 后缀自动机 (SAM) 后缀平衡树 广义后缀自动机 后缀树
Manacher
最长回文 HDU - 3068求最长回文串的长度【马拉车算法Manacher】
回文树 序列自动机 最小表示法 Lyndon 分解
