KMP替代算法——字符串Hash

编程 数据结构 速记

今天来谈谈一种用来替代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)

注释

1. hash(i,j)表示i~j的hash值
2. 再进行实际代码书写时，需要注意取模及负数的情况（详见代码）
3. 这里因为字符串由小写字母构成，使用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.