【字符串】哈希
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} 搬运过来的…… - 于是作者进行了重新翻译:
- 作者题解都写好了。