字符串Hash 学习笔记

模板及讲解
字符串Hash的核心就是把原本$O(n)$比较两个字符串变成$O(1)$比较两个Hash值(整数)。
双Hash:
两个模数$MO1,MO2$(最好为质数,$19260817, 19660813$),只有两个模数的值都相同才判定Hash值相同
BASE:大于所有字符串取值的一个数,不能包含模数的质因子
求Hash值:
$$Hash=(s_1 \times BASE^{n-1}+ s_2 \times BASE^{n-2} + … + s_n) \mod MO$$

快速hash一个字符串的所有子串:先对串的所有前缀Hash,记为$Hash_i​$,设$p_i=BASE^i​$,则
$$Hash_i=(Hash_{i-1} \times s_i) \mod MO$$
$$Hash_{i, j}=(Hash_{r} - Hash_{l-1} \times p_{r-l+1}) \mod MO$$
$Hash_{i, j}$即为答案。

常见题型:

相关代码:
Luogu 3370,双Hash模板

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
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define ull unsigned long long
using namespace std;
const int MAXN = 10000 + 5;
ull BASE = 300, MO1 = 19260817, MO2 = 19660813;
struct data {
ull a, b;
bool operator < (const data &y) const {
return a < y.a;
}
}a[MAXN];
int n;
char ch[1500 + 5];
int hash1(char *s) {
int len = strlen(s);
ull ret = 0;
for (int i = 0; i < len; i++) ret = (ret * BASE + (ull)s[i]) % MO1;
return ret;
}
int hash2(char *s) {
int len = strlen(s);
ull ret = 0;
for (int i = 0; i < len; i++) ret = (ret * BASE + (ull)s[i]) % MO2;
return ret;
}
void clean() {
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
scanf("%s", ch);
a[i].a = hash1(ch), a[i].b = hash2(ch);
}
sort(a + 1, a + 1 + n);
int ans = 1;
for (int i = 2; i <= n; i++) {
if (a[i].a != a[i - 1].a || a[i].b != a[i - 1].b) ans++;
}
printf("%d\n", ans);
}
int main() {
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------