Hash 学习笔记

发表于 | 分类于 | | + s

模板及讲解

字符串Hash的核心就是把原本$O(n)$比较两个字符串变成$O(1)$比较两个Hash值(整数)。

Hash的方法取决于是否会冲突，这里运用不同模数巧妙解决冲突
因为字符串相等、字符串ASCII码前缀和具有单调性，所以经常用固定左端点二分右端点来解决问题(有时用二分查找、map、桶、排序等解决问题)

BASE 选取：
1、不要将任何数对应到 0 ，例如将 A对应到0 则无法区分AB、B
2、大于$max($对应数$)$

双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}$即为答案。

const ULL BS = 300;
ULL hsh[MAXN], p[MAXN];

p[0] = 1;
for (int i = 1; i <= n; i++) p[i] = p[i - 1] * BS, hsh[i] = hsh[i - 1] * BS + (s[i] - 'a');

inline ULL getH(int x, int y) {return hsh[y] - hsh[x - 1] * p[y - x + 1];}

运用 unsigned long long 的自然溢出完成取模(能双Hash就双Hash，自然溢出很容易被卡)。

二维 Hash

例题：Bzoj 2351

给行列分别hash一次，行先hash，然后将hash值再hash一次，即hash列

然后查询子矩阵Hash值直接像二维前缀和一样做即可，类比于一维的 Hash 方法

树 Hash

对于有根树的 Hash。无根树找重心当根。

$h[x]$表示$x$为根的子树的hash​，$g[x]$表示$x$为根时全树的​hash​。
$$
h[x] = 1 + \sum_{y \in \text{son}(x)} h[y] \times p[\text{siz}[y]] \\
g[x] = (g[fa] - h[x] \times p[\text{siz}[x]]) \times p[n-\text{siz}[x]] + h[x]
$$

例题1: BJOI2015 树的同构
例题2: JSOI2016 独特的树叶

相关代码

Luogu 3370，双Hash模板

#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;
}
------ 本文结束 ------