2020-2021:teams:legal_string:字符串哈希_lgwza
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:字符串哈希_lgwza [2020/07/15 18:48] lgwza 创建 |
2020-2021:teams:legal_string:字符串哈希_lgwza [2020/07/15 18:49] (当前版本) lgwza |
||
|---|---|---|---|
| 行 55: | 行 55: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| + | ===== Hash 的分析与改进 ===== | ||
| + | |||
| + | ==== 错误率 ==== | ||
| + | |||
| + | 若进行 $n$ 次比较，每次错误率 $\frac{1}{M}$，那么总错误率是 $1-(1-\frac1M)^n$。在随机数据下，若 $M=10^9+7,n=10^6$，错误率约为 $\frac1{1000}$，并不是能够完全忽略不计的。 | ||
| + | |||
| + | 所以，进行字符串哈希时，经常会对两个大质数分别取模，这样的话哈希函数的值域就能扩大到两者之积，错误率就非常小了。 | ||
| + | |||
| + | ==== 多次询问子串哈希 ==== | ||
| + | |||
| + | 单次计算一个字符串的哈希值复杂度是 $O(n)$，其中 $n$ 为串长，与暴力匹配没有区别，如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。 | ||
| + | |||
| + | 一般采取的方法是对整个字符串先预处理出每个前缀的哈希值，将哈希值看成一个 $b$ 进制的数对 $M$ 取模的结果，这样的话每次就能快速求出子串的哈希了： | ||
| + | |||
| + | 令 $f_i(s)$ 表示 $f(s[1..i])$，那么 $f(s[l..r])=\frac{f_r(s)-f_{l-1}(s)}{b^{l-1}}$，其中 $b^{l-1}$ 也可以预处理出来，用乘法逆元或者是在比较哈希值时等式两边同时乘上 $b$ 的若干次方化为整式均可。 | ||
| + | |||
| + | 这样的话，就可以在 $O(n)$ 的预处理后每次 $O(1)$ 地计算子串的哈希值了。 | ||
| + | |||
| + | ===== Hash 的应用 ===== | ||
| + | |||
| + | ==== 字符串匹配 ==== | ||
| + | |||
| + | 求出模式串的哈希值后，求出文本串每个长度为模式串长度的子串的哈希值，分别与模式串的哈希值比较即可。 | ||
| + | |||
| + | ==== 最长回文子串 ==== | ||
| + | |||
| + | 二分答案，判断是否可行时枚举回文中心（对称轴），哈希判断两侧是否相等。需要分别预处理正着和倒着的哈希值。时间复杂度 $O(n\log n)$。 | ||
| + | |||
| + | 这个问题可以使用 manacher 算法在 $O(n)$ 的时间内解决。 | ||
| + | |||
| + | ===== 参考链接 ===== | ||
| + | |||
| + | [[https://oi-wiki.org/string/hash/|Oi Wiki]] | ||
2020-2021/teams/legal_string/字符串哈希_lgwza.1594810122.txt.gz · 最后更改: 2020/07/15 18:48 由 lgwza
