【6】Hash 学习笔记

Eason_cyx · 2025-07-01 15:28:48 · 算法·理论

简单来说，Hash 就是通过一个函数，将每一个字符串一一对应到一个整数上来加快比较速度的算法。

Hash 算法的优点是可以快速解决正解是其他字符串算法复杂问题，缺点是可能会被卡。因此，人们创造了多种 Hash 方法。

这里介绍较优的一种：BKDRHash。

现在给定一个字符串 s，它的长度为 n。

此时，我们可以寻找一个底数 b 和一个模数 p，然后将 s 看成一个 b 进制数。

具体地，假设 s_i 的 ASCII 码是 a(i)，那么这个字符串 s 的 Hash 值 h(s) 为：

知道了该字符串怎么求 Hash 之后，我们可以求出其任意一个子串的 Hash 值。

我们定义 h'(s,k) 表示 s_1 \sim s_k 这个串的 Hash 值。根据上面 h(s) 的式子，我们可以得到一个递推式子：

于是，我们可以在 O(n) 的时间里算出所有的 h'(s,k)。

那么我们如何找到 s_l \sim s_r 的哈希值？

回想一下我们是怎么在一个十进制数中找到一段的：例如，我们要在数 1234567009 中找到第 7 \sim 10 位。我们可以做一个竖式减法来完成：

（\LaTeX 不好，见谅qwq）

上面竖式可以写成：1234567009-123456\times10^4=7009。这给了我们启发：b 进制数也是一样的！确实。所以，我们可以通过如下方法求出 s_l \sim s_r 的哈希值：

又：在应用中一般使用 b=131 或 b=13131，p=2^{64} 或一个大质数不容易被卡。也可以选择双模哈希进一步减小被卡风险，关于卡哈希请参考 Hash Killer 系列题目，以及推荐阅读：Blowing up unordered_map, and how to stop getting hacked on it - By neal, CodeForces。

P3370 【模板】字符串哈希

给定 n 个字符串，求其中有多少个不同的字符串。

直接将每个字符串的 Hash 值求出来，然后丢进一个数组。于是问题就变成了有多少个不同的整数。排序即可。

时间复杂度 O(\sum M_i+n \log n)，可以通过。

#include <bits/stdc++.h>
using namespace std;
const int base = 919,mod = 998244353;
int hhash(string s) {
    int x = 0;
    for(int i = 0;i < s.size();i++) 
        x = (base * x + s[i] - '0') % mod;
    return x;
}
int a[200005];
int main() {
    int n; cin >> n;
    for(int i = 1;i <= n;i++) {
        string x; cin >> x;
        a[i] = hhash(x);
    }
    sort(a+1,a+n+1);
    int cnt = 0;
    for(int i = 1;i <= n;i++) 
        if(a[i] != a[i-1]) cnt++;
    cout << cnt;
    return 0;
}

P10468 兔子与兔子

给定字符串 s 和 m 次询问，每次给定 l_1,r_1,l_2,r_2，判断 s_{l_1} \sim s_{r_1} 是否与 s_{l_2} \sim s_{r_2} 完全相同。

可以直接用刚才的求子串哈希值的方法，只需预处理出 b 的次幂，O(1) 即可求解。

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long; const ull base = 131;
ull h[1000005], y[1000005]; ull Hash(int l, int r) {
    return h[r] - h[l-1] * y[r-l+1];
} int main() {
    string s; cin >> s; s = ' ' + s; 
    for(int i = 1;i < s.size();i++) h[i] = h[i-1] * base + (s[i] - 'a') + 1;
    y[0] = 1; for(int i = 1;i < s.size();i++) y[i] = y[i-1] * base;
    int q; cin >> q; while(q--) { int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
        if(Hash(l1, r1) == Hash(l2, r2)) cout << "Yes\n"; else cout << "No\n";
    } return 0;
}

P10469 后缀数组

求所有的 \text{SA}_i 和 \text{Height}_i，定义见原题。

可以考虑对于每一个位置二分答案，二分长度之后拿哈希判断是否相等。时间复杂度 O(n \log^2 n)，数据范围较小，可以通过。

（P.S. 将 sort 改成 stable_sort 就可以过原板子 qwq）

#include <bits/stdc++.h>
using namespace std;
string s; int n;
using ull = unsigned long long;
ull hs[300005], p[300005]; 
const ull base = 131;
ull qry(int l, int r) { return hs[r] - hs[l-1] * p[r-l+1]; }
struct SA { int x; } a[300005]; 
bool cmp(SA x, SA y) {
    int xx = x.x, yy = y.x;
    //看[xx, n] 和 [yy, n] 的字典序大小 
    int l = 0, r = n-max(xx, yy);
    if(r == 1) return (s[xx] != s[yy] ? s[xx] < s[yy] : s[xx+1] < s[yy+1]);
    while(l < (r-1)) {
        int mid = (l + r) >> 1;
        if(qry(xx, xx+mid-1) == qry(yy, yy+mid-1)) l = mid;
        else r = mid - 1;
    } if(qry(xx, xx+r-1) == qry(yy, yy+r-1)) return s[xx+r] < s[yy+r];
    else return s[xx+l] < s[yy+l];  
} int main() { p[0] = 1;
    cin >> s; n = s.size(); s = s + ' '; hs[0] = s[0];
    for(int i = 1;i < n;i++) 
        hs[i] = hs[i-1] * base + s[i], p[i] = p[i-1] * base;
    for(int i = 0;i < n;i++) a[i].x = i;
    sort(a, a+n, cmp);
    for(int i = 0;i < n;i++) cout << a[i].x << " \n"[i == n-1]; 
    cout << 0 << " "; for(int i = 1;i < n;i++) {
        int xx = a[i].x, yy = a[i-1].x;
        int l = 0, r = n-max(xx, yy);
        if(r == 1) cout << (s[xx] == s[yy] ? 1 : 0) << " ";
        else {
            while(l < (r-1)) {
                int mid = (l + r) >> 1;
                if(qry(xx, xx+mid-1) == qry(yy, yy+mid-1)) l = mid;
                else r = mid - 1;
            } if(qry(xx, xx+r-1) == qry(yy, yy+r-1)) cout << r << " ";
            else cout << l << " ";
        }
    }
    return 0;
}