很久以前写的。。。
今天来谈谈一种用来替代KMP算法的奇葩算法——字符串Hash
例题:给你两个字符串p和s,求出p在s中出现的次数。(字符串长度小于等于1000000)
字符串的Hash
根据字面意思,这种算法是以Hash为基础的,要Hash,就必须要将字符串转化为数字;假设这两个字符串是26个字母组成的,那么我们就可以把它们看成两个26进制的数。
但是因为字符串很长,这个数肯定是很大的,用int64(long long)存不下,那么怎么办呢?我们可以用Hash来取模,使这个数字缩小到我们可以接受的范围内。于是我们就想到了除法Hash。
Hash最重要的是解决重复,一般而言,Hash有两种方式:线性探查法、链接法,但是这两种都是以存储来解决重复的,如果要把这些字符串都存下来,空间也是不可接受,所以我们不能将这些字符串存下来以避免重复。
既然这样,我们只能求助于概率。根据生日悖论,如果取模的这个数大于等于n^2,那么冲突概率会降到50%以下,可以接受。于是我们使用100000007这个质数,概率约为50%。
这已经足够了。
两组Hash
但是,50%的概率还是有一点高。我们可以使用两组Hash来解决。
我们知道,对于任意两个数a,b,若a=b,那么无论取模的值p是多少,Hash(a)恒等于Hash(b)。也就是说,不管如何取模,两个相同的数都会被认为是相等的。所以我们可以取多个模数来降低冲突概率。如果取1个模,冲突概率为50%,那么同时取2个模的冲突概率绝对低于25%,是一个很小的概率。(一般而言,我们会取1000000007,1000000009,但是已经有被共享的数据可以冲突)
Hash的加减性
仅仅是上面这些,对付例题还不够,因为我们生成一个字符串的Hash还是需要一位一位地累加,这每次会消耗O(len)的时间,很不划算。怎么办呢?
我们可以运用前缀和的思想。例如:对于如下的s
s="abcdefghij"
假设需要查找一个长度为3的字符串,那么需要比较的字符串是
abc
bcd
cde
efg
.....
可以看到,子串1(abc)和子串2(bcd)有两个字母bc是重复的,而我们之前的操作重复计算了bc的值,存在重复,这是我们优化的突破口。我们该如何避免这样的重复呢?当然是记录下来,类比片段和,片段和也是类似的通过数字的记录、加减来避免重复、快速计算。Hash的加减也和片段和差不多,只是需要注意位的对齐。
公式如下 Hash(i,j)=hash(1,j)-hash(1,i-1)*31^(j-i+1)
注释
- hash(i,j)表示i~j的hash值
- 再进行实际代码书写时,需要注意取模及负数的情况(详见代码)
- 这里因为字符串由小写字母构成,使用31这个进制足够大,并且31是一个质数,不像26一样容易产生重复
演示代码(Pascal)
var
s1,s2:ansistring;
n,m,i,p1,p2,ans:longint;
key1,key2,value1,value2:int64;
h1,h2,mi1,mi2:array[0..1000005] of int64;
begin
readln(s1);
readln(s2);
p1:=100000007;
p2:=100000009;
m:=length(s1);
key1:=0;
key2:=0;
for i:=1 to m do
begin
key1:=(key1*31+ord(s1[i])-96) mod p1;
key2:=(key2*31+ord(s1[i])-96) mod p2;
end;
n:=length(s2);
h1[0]:=0; mi1[0]:=1;
h2[0]:=0; mi2[0]:=1;
for i:=1 to n do
begin
h1[i]:=(h1[i-1]*31+ord(s2[i])-96) mod p1;
h2[i]:=(h2[i-1]*31+ord(s2[i])-96) mod p2;
mi1[i]:=mi1[i-1]*31 mod p1;
mi2[i]:=mi2[i-1]*31 mod p2;
end;
ans:=0;
for i:=1 to n-m+1 do
begin
value1:=(h1[i+m-1]-h1[i-1]*mi1[m] mod p1+p1) mod p1;
value2:=(h2[i+m-1]-h2[i-1]*mi2[m] mod p2+p2) mod p2;
if (value1=key1) and (value2=key2) then inc(ans);
end;
writeln(ans);
end.