字符串哈希

前言

字符串哈希号称是学了后再遇到字符串题就可以丢掉kmp的算法哈哈（当然bushi）。

它是一种将字符串映射成数字的算法，如何映射的呢？
利用的就是hash，其方式是将一个给定的字符串转成 $P$进制的数字，即对字符串每个位置$i$上的字符赋予一个权值$P^i$（这个权值从左到右依次递减），然后用一个数字取替该字符（一般来讲用的是字符对应ASCII码值）并乘上权值后相加起来，可以预想到此时的值会非常地庞大，所以再给它mod上一个限定值$Q$。
用公式表示就是：

字符串 —> $s_1{s}_2{s}_3{s}_4......s_{n-1}{s}_n$。
哈希值—>$(s_1\times P^{n-1}+s_2\times P^{n-2}+s_3\times P^{n-3}+......s_{n-1}\times P^1+s_n\times P^0)\%Q$。

如果让h[i]存字符串$s[1...i]$的hash值，也即整个字符串的hash值存在h[n]里面；
代入上述公式有：

$h[1]=s[1]$,
$h[2]=s[1]\times P+s[2]$
$h[3]=s[1]\times P^2+s[2]\times P+s[3]$
$h[4]=s[1]\times P^3+s[2]\times P^2+s[3]\times P+s[4]$
… …
(先不显示$\%Q$)
由此，就可以得到一个递推式：$h[i]=h[i-1]\times P+s[i]，i\in [1,n]$。

那么观察一下就可以发现递推式有点点像一个前缀和公式，其实也就说明了可以从$1$到$n$递推地求出个各个h[]值，不仅如此，进一步拓展还可以再求字符串某个子串的hash值：

例如，子串$s[2..4]$的hash值=$s[2]\times P^2+s[3]\times P+s[4]$，同时，也＝$h[4]-h[2-1]\times P^{4-2+1}$，因此还得到一个区间和的公式：$h[l,r]=h[r]-h[l-1]\times P^{r-l+1}$。

---

解决hash冲突

有了映射，那么有个值得注意的问题就是如何解决hash冲突（这里是hash值相等的情况）。

• 首先，每个代表字符的数字不能为0，举个例子，若用0代替字符'A'，那么对于字符串"A"、"AAA"、"AAAAAA"来讲，它们的hash值均为0，这就引起冲突大了！所以要以非0的数字代替字符以区别开。
• 由经验之谈，$P$一般设置成131，$Q$设置成$2^{64}$时，各种字符串映射出的hash值不相等的概率为$99.99\%$（据说），那么此时就可以近似地认为不产生冲突。

有了上述定义后，思考一个问题，如何比较两个字符串是否相等，那就简单了，先将它们都进行hash映射，然后对其hash值进行比较是否相等作为依据就可以了，由于是整数上的比较，那么该操作的复杂度仅仅只有$O(1)$。

---

并不真正地使用$\%Q$

一般来讲，用C++写的话并不需要在每次计算hash值时$\%Q$，转而可以考虑使用unsigned long long(ULL)数据类型来存，用这种数据类型有啥好处呢？一是存的数值比较大，适合拿来映射大数据量的字符串，二是当一个ULL的数溢出时，编译器自动会将这个数进行$\%2^{64}$处理，这正好是跟$Q$设置成$2^{64}$时期望吻合的啊。

有关更多字符串哈希的数学解释以及详细定义还可参考：字符串哈希 - OI Wiki。

---

字符串哈希 #1

给定一个长度为 n 的字符串，再给定 $m$ 个询问，每个询问包含四个整数 $l_1,r_1,l_2,r_2$，请你判断 $[l_1,r_1]$ 和 $[l_2,r_2]$ 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数 $n$ 和 $m$，表示字符串长度和询问次数。

第二行包含一个长度为 $n$ 的字符串，字符串中只包含大小写英文字母和数字。

接下来 $m$ 行，每行包含四个整数 $l_1,r_1,l_2,r_2$，表示一次询问所涉及的两个区间。

注意，字符串的位置从 $1$ 开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围
$1\le n,m\le 10^5$

输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
1
2
3
4
5

输出样例：

Yes
No
Yes
1
2
3

---

Code

#include 
#include 
using namespace std;
typedef unsigned long long ULL;

const int N = 1e5 + 10, P = 131;

ULL h[N];
ULL p[N];       //p[i]其实就是存P的i次方
char s[N];
int n, m;

ULL get(int l, int r){      //子串s[l...r]的hash值
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main(){
    ios :: sync_with_stdio(false);
    
    cin >> n >> m;
    cin >> s + 1;
    p[0] = 1;
    
    //预处理hash值
    for(int i = 1;i <= n;i ++){
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    
    while(m --){
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int h1 = get(l1, r1), h2 = get(l2, r2);
        if(h1 == h2)        cout << "Yes" << endl;
        else                cout << "No" << endl;
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

洛谷 P3370 - 字符串哈希 #2

如题，给定 $N$ 个字符串（第 $i$ 个字符串长度为 $M_i$，字符串内包含数字、大小写字母，大小写敏感），请求出 $N$ 个字符串中共有多少个不同的字符串。

友情提醒：如果真的想好好练习哈希的话，请自觉，否则请右转PJ试炼场:)

输入格式

第一行包含一个整数 $N$，为字符串的个数。

接下来 $N$ 行每行包含一个字符串，为所提供的字符串。

输出格式

输出包含一行，包含一个整数，为不同的字符串个数。

样例 #1

样例输入 #1

5
abc
aaaa
abc
abcc
12345
1
2
3
4
5
6

样例输出 #1

4
1

提示

对于 $30\%$ 的数据：$N\le 10$，$M_i\approx 6$，$Mmax\le 15$。

对于 $70\%$ 的数据：$N\le 1000$，$M_i\approx 100$，$Mmax\le 150$。

对于 $100\%$ 的数据：$N\le 10000$，$M_i\approx 1000$，$Mmax\le 1500$。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

---

Code

#include 
#include 
#include 
using namespace std;
typedef unsigned long long ULL;

const int N = 1e5 + 10, P = 131;

ULL hs[N];      //存字符串的hash值
int n;
char s[1510];

ULL get(){
    int len = strlen(s + 1);
    int h = 0, p = 1;
    for(int i = 1;i <= len;i ++){
        h = h * p + s[i];
        p *= P;
    }

    return h;
}

int main(){
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 0;i < n;i ++){
        cin >> s + 1;
        hs[i] = get();
    }

    sort(hs, hs + n);

    int ans = 1;
    for(int i = 1;i < n;i ++){
        if(hs[i] != hs[i - 1])      ans ++;
    }

    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

总结

可以看到，经过一遍hash值的预处理后，给后续子串之间的查询操作带来了极大的方便，让原本繁琐的字符串匹配转变成了只是数字上的比较。