DDOSvoid's Blog

字符串hash

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

简介

$hash$ 的一种

最常用的 $hash$ 一般是进制 $hash$，大概就是把字符串看成一个大数

一般情况下模数选用 $10^{18}$ 级别的，但这个时候就需要 $O(1)$ 乘

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
struct Hash {
    const int base = 131;
    const ll p = 212370440130137957;

    ll pow[maxn], h[maxn];

    inline ll mul(ll x, ll y) {
        return (x * y - (ll) ((long double) x / p * y) * p + p) % p;
    }
    inline ll add(ll x, ll y) { return (x += y) >= p ? x - p : x; } 

    void init(char *s) {
        int l = strlen(s + 1); 
        pow[0] = 1; for (int i = 1; i <= l; ++i) pow[i] = mul(pow[i - 1], base);
        for (int i = 1; i <= l; ++i)
            h[i] = add(s[i], mul(h[i - 1], base));
    }
    ll get(int l, int r) { return add(h[r], p - mul(h[l - 1], pow[r - l + 1])); }
    ll hash(char *s) {
        int l = strlen(s + 1); ll ans = 0;
        for (int i = 1; i <= l; ++i)
            ans = add(s[i], mul(ans, base));
        return ans;
    }
} h;

如果模数在 $1e9$ 以内的话，还是建议使用双 $hash$，而且这个明显要快很多，主要是因为膜大数的时间会比较长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int b1 = 131, b2 = 13131; 
const ll p1 = 999999937, p2 = 1000000033;
struct Hash {
    int pow[maxn], h[maxn], p, base;

    inline int mul(int x, int y) { return 1ll * x * y % p; }
    inline int add(int x, int y) { return (x += y) >= p ? x - p : x; } 

    void init(char *s, int _base, int _p) {
        int l = strlen(s + 1); p = _p; base = _base;
        pow[0] = 1; for (int i = 1; i <= l; ++i) pow[i] = mul(pow[i - 1], base);
        for (int i = 1; i <= l; ++i)
            h[i] = add(s[i], mul(h[i - 1], base));
    }
    int get(int l, int r) { return add(h[r], p - mul(h[l - 1], pow[r - l + 1])); }
    int hash(char *s) {
        int l = strlen(s + 1); int ans = 0; 
        for (int i = 1; i <= l; ++i)
            ans = add(s[i], mul(ans, base));
        return ans;
    }
} h1, h2;

最快但也是最容易挂的做法，模数直接取 $2^32$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Hash {
    const int base = 131;
    
    uint pow[maxn], h[maxn];

    void init(char *s) {
        int l = strlen(s + 1); 
        pow[0] = 1; for (int i = 1; i <= l; ++i) pow[i] = pow[i - 1] * base;
        for (int i = 1; i <= l; ++i)
            h[i] = s[i] + h[i - 1] * base;
    }
    uint get(int l, int r) { return h[r] - h[l - 1] * pow[r - l + 1]; }
    uint hash(char *s) {
        int l = strlen(s + 1); uint ans = 0; 
        for (int i = 1; i <= l; ++i)
            ans = s[i] + ans * base;
        return ans;
    }
} h;