首页 > 笔记 > 字符串Hash总结

字符串Hash总结

Hash是什么意思呢?某度翻译告诉我们:

hash 英[hæʃ] 美[hæʃ]
n. 剁碎的食物; #号; 蔬菜肉丁;
vt. 把…弄乱; 切碎; 反复推敲; 搞糟;

我觉得Hash是引申出 把...弄乱 的意思。

今天就来谈谈Hash的一种——字符串hash。

据我的理解,Hash就是一个像函数一样的东西,你放进去一个值,它给你输出来一个值。输出的值就是Hash值。一般Hash值会比原来的值更好储存(更小)或比较。

那字符串Hash就非常好理解了。就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值。

字符串Hash的种类还是有很多种的,不过在信息学竞赛中只会用到一种名为“BKDR Hash”的字符串Hash算法。

它的主要思路是选取恰当的进制,可以把字符串中的字符看成一个大数字中的每一位数字,不过比较字符串和比较大数字的复杂度并没有什么区别(高精数的比较也是$O(n)$的),但只要把它对一个数取模,然后认为取模后的结果相等原数就相等,那么就可以在一定的错误率的基础上$O(1)$进行判断了。

那么我们选择什么进制比较好?

首先不要把任意字符对应到数字0,比如假如把a对应到数字0,那么将不能只从Hash结果上区分ab和b(虽然可以额外判断字符串长度,但不把任意字符对应到数字0更加省事且没有任何副作用),一般而言,把a-z对应到数字1-26比较合适。

关于进制的选择实际上非常自由,大于所有字符对应的数字的最大值,不要含有模数的质因子(那还模什么),比如一个字符集是a到z的题目,选择27、233、19260817 都是可以的。

模数的选择(尽量还是要选择质数):

绝大多数情况下,不要选择一个$10^9$级别的数,因为这样随机数据都会有Hash冲突,根据生日悖论,随便找上$\sqrt{10^9}$个串就有大概率出现至少一对Hash 值相等的串(参见BZOJ 3098 Hash Killer II)。

最稳妥的办法是选择两个$10^9$级别的质数,只有模这两个数都相等才判断相等,但常数略大,代码相对难写,目前暂时没有办法卡掉这种写法(除了卡时间让它超时)(参见BZOJ 3099 Hash Killer III)。

如果能背过或在考场上找出一个$10^18$级别的质数(Miller-Rabin),也相对靠谱,主要用于前一种担心会超时,后一种担心被卡。

偷懒的写法就是直接使用unsigned long long,不手动进行取模,它溢出时会自动对$2^64$进行取模,如果出题人比较良心,这种做法也不会被卡,但这个是完全可以卡的,卡的方法参见BZOJ 3097 Hash Killer I。

用luogu P3370为例。

这是自然溢出hash(100)

这是单模数hash(80)

这是双hash(100)

这是只用一个10^18质数的hash(100)

Hash还有一方面,就是它可以处理子串信息。对于一个字符串,我们可以预处理它$1-l$的hash值,这样$l+1$的hash值就可以$O(1)$的递推出来。

对于一个字符串$l-r$的子串,我们可以用$f[r]-b^{r-l+1}f[l-1]$来求出来,其中b表示进制。

这样的话hash就可以水过字符串匹配的题目

cogs1570

【题目描述】

法国作家乔治·佩雷克(Georges Perec,1936-1982)曾经写过一本书,《敏感字母》(La disparition),全篇没有一个字母‘e’。他是乌力波小组(Oulipo Group)的一员。下面是他书中的一段话:

Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…

佩雷克很可能在下面的比赛中得到高分(当然,也有可能是低分)。在这个比赛中,人们被要求针对一个主题写出甚至是意味深长的文章,并且让一个给定的“单词”出现次数尽量少。我们的任务是给评委会编写一个程序来数单词出现了几次,用以得出参赛者最终的排名。参赛者经常会写一长串废话,例如500000个连续的‘T’。并且他们不用空格。

因此我们想要尽快找到一个单词出现的频数,即一个给定的字符串在文章中出现了几次。更加正式地,给出字母表{'A','B','C',...,'Z'}和两个仅有字母表中字母组成的有限字符串:单词W和文章T,找到W在T中出现的次数。这里“出现”意味着W中所有的连续字符都必须对应T中的连续字符。T中出现的两个W可能会部分重叠。

【输入格式】

输入包含多组数据。

输入文件的第一行有一个整数,代表数据组数。接下来是这些数据,以如下格式给出:

第一行是单词W,一个由{'A','B','C',...,'Z'}中字母组成的字符串,保证1<=|W|<=10000(|W|代表字符串W的长度)

第二行是文章T,一个由{'A','B','C',...,'Z'}中字母组成的字符串,保证|W|<=|T|<=1000000。

【输出格式】

对每组数据输出一行一个整数,即W在T中出现的次数。

【样例输入】

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

【样例输出】

1
3
0

代码

写到这里突然发现hash好像可以暴力水过很多字符串算法。。

1、kmp

问题:给两个字符串S1,S2,求S2是否是S1的子串,并求S2在S1中出现的次数

把S2 Hash出来,在S1里找所有长度为$|S2|$的子串,Hash比较。效率$O(|S1|)$

2、AC自动机

问题:给N个单词串,和一个文章串,求每个单词串是否是文章串的子串,并求每个单词在文章中出现的次数。

把每一个单词hash成整数,再把文章的每一个子串hash成整数,接下来只需要进行整数上的查找即可。

复杂度:$O(|A|^2+|S|)$

用AC自动机可以做到$O(|A|+|S|)$的复杂度,$|S|$是单词串总长,$|A|$是文章长度

3、后缀数组

问题:给两个字符串S1,S2,求它们的最长公共子串的长度。

将S1的每一个子串都hash成一个整数,将S2的每一个子串都hash成一个整数

两堆整数,相同的配对,并且找到所表示的字符串长度最大的即可。

复杂度:$O(|S1|^2+|S2|^2)$

用后缀数组可以优化到$O(|S| log|S|)$

4、马拉车

问题:给一个字符串S,求S的最长回文子串。

先求子串长度位奇数的,再求偶数的。枚举回文子串的中心位置,然后二分子串的长度,直到找到一个该位置的最长回文子串,不断维护长度最大值即可。

复杂度:$O(|S| log|S|)$

用manacher可以做到$O(|S|)$的复杂度

5、扩展kmp

问题:给一个字符串S,求S的每个后缀与S的最长公共前缀

枚举每一个后缀的起始位置,二分长度,求出每个后缀与S的最长公共前缀。

复杂度:$O(|S| log|S|)$

用extend-kmp可以做到$O(|S|)$的复杂度

后记

hash真是一种优雅的暴力。

因为字符串特殊的性质,我们可以二分得处理它,一般都有单调性。


12 COMMENTS

  1. krama2017-08-11 下午9:49

    %%%%dalao

  2. attack2017-08-12 上午10:50

    666666666666666666666

  3. dp2332017-08-20 下午1:12

    :evil: 兹瓷滋糍

  4. Hans2017-10-17 上午7:53

    kmp那一部分“在S1里找所有长度为|S1|的子串”....个人认为是找长度为|S2|的子串?

  5. Hans2017-10-17 上午7:55

    还有我不太清楚效率为什么是O(|S2|)的= =

  6. vanilla2017-10-23 下午9:31

    又涨知识了

  7. Chs2018-03-09 下午11:13

    请问自然溢出中的 return ans&0x7fffffff; 的位运算是什么意思

    • 远航之曲2018-03-10 下午1:42

      因为溢出后符号会变负,这样操作后就变成正的了。

      • Chs2018-03-13 上午12:03

        但是不是返回的是无符号吗?为什么会有负的

        • 远航之曲2018-03-13 上午7:06

          Sorry说错了。。应该是截取了它小于int的部分。。0x7fffffff是maxint,这样and一下相当于取模了。

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×