【字符串】哈希
WeLikeStudying · · 个人记录
-
\color{white}\text{Hash little baby!Hash!} -
\color{white}\text{作者偶然皮一下很开心。} -
\color{white}\text{兄弟们，乱搞能过当然要乱搞！}
哈希
- 思路主要是把字符串当成数看待。
- 常用的编码是：
\sum_{i=0}^na_ib^i\bmod p - 然后忽略可能的冲突。（？根据生日攻击，首次冲突的次数可能是
\sqrt p 级别的） - 如果愿意可以使用双哈希。
- 还有一句忠告，设
b^m\bmod p=b 成立的最小的m 不要太小。 - 常见模数：
19260817 33333331 23252729 998244353 10^9+7 9223372036854775783(?
哈希表
- 与哈希的思想类似，但不同的是我们必须开一个跟模数
p 同规模的表，冲突不可避免。 - 放一张以前写杜老师筛法时打的代码（最朴素的线性寻址，被证明在平均情况下接近
O(n) ）。 - 其实还有很多做法，但作者这里就不介绍了，不过这样即使没有被针对还是有一定常数。
- 还有一个有趣的小问题：哈希表存字符串怎么办？
- 拿三个质数，规模大概分别在
10^9,10^9,10^7 左右，先双哈希成长整型再放进哈希表（感觉很迷）。 - 还有更迷的，你可以以这
3 个质数为依据来一个3 哈希，然后前两个质数编码成长整型，以第3 个质数为关键字放入哈希表，出错率\frac1{1000000000000000000000000} 。
例题
- 由于内容并不多居然在这里开例题了！
- 例题。
- 题意简述：给定
n 个字符，支持3 个操作：合并字符串，分离字符串，统计所有字符串中，与s 有相同的长度为k 字串的串的个数，k\le 50 。 - 其实就是哈希表存字符串的实际应用了。
- 所以很水了，但作者发现自己并不会链表 QWQ。
- 时间复杂度毛估估大概是
O(nk+ck^2+\sum|s|) ，卡常后可以通过此题。 - 然后并没有卡常就过了。。（但作者向左和向右延伸的
l 和r 看错了，作者调试的时候脑袋需要转一下啊）。 - 作者在这里偷了个懒，采用整型溢出的做法来求。
- 代码实现。
再来一发
- 例题。
- 作者发现自己并不知道啥是独立集，于是去百度了一下：独立集就是一些点，它们之间互相没有连边。
- 但作者觉得这样还是不太清楚：主要原因就是它是从某
\text{OJ} 搬运过来的…… - 于是作者进行了重新翻译：
- 作者题解都写好了。