hash

发表于 | 更新于: | 分类于 | | 阅读数

遇到hash的题目默默流下眼泪😥

小w的a=b问题

题意：给你两个数组a和b，长度为n和m，问你$\prod_{i=1}^{n}a_i ! $是否等于$\prod_{i=1}^{m}b_i ! $，其中$1 \leq n,m \leq 10^5$,$0 \leq a_i,b_i \leq 10^5$

初次遇到这种题目，我以为是一个推公式的题目，把我整懵了，果然数据结构的知识还是灰常重要啊[点头]

思路：用两个比较大一点的质数作为模系，然后计算每个阶乘$(0 \sim10^5)$所在模系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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
ll mod1=1e9+7,mod2=1e9+9;
ll m1[maxn],m2[maxn];
ll t,n,m,a;
void init(){
    m1[0]=m2[0]=1;
    for(ll i=1; i<maxn; i++){
        m1[i]=m1[i-1]*i%mod1;
        m2[i]=m2[i-1]*i%mod2;
    }
}
int main(){
    init();
    scanf("%lld",&t);
    while(t--){
        scanf("%lld %lld",&n,&m);
        ll s1=1,s2=1,s3=1,s4=1;
        for(ll i=0; i<n; i++){
            scanf("%lld",&a);
            s1=s1*m1[a]%mod1;
            s2=s2*m2[a]%mod2;
        }
        for(ll i=0; i<m; i++){
            scanf("%lld",&a);
            s3=s3*m1[a]%mod1;
            s4=s4*m2[a]%mod2;
        }
        if(s1==s3 && s2==s4) puts("equal");
        else puts("unequal");
    }
}

字符串hash

上面是数字的hash，而字符串的hash就是一个$O(n)$的预处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef unsigned long long ull;
//ull 会溢出取模
const ull base=233;
const int maxn=1e5+10;
char s[maxn];
ull hs[maxn],p[maxn];
ull geths(int l,int r){
    return (ull)hs[r]-p[r-l+1]*hs[l-1];
}
void init(){
    p[0]=1;
    for(int i=1; i<maxn; i++) p[i]=p[i-1]*base;
}
int main(){
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=1; i<=len; i++){
        hs[i]=hs[i-1]*base+s[i];
    }
}

手写hash，可以替代map加速查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Hash{
    ll mod = 2908361;
    ll cnt = 0, Head[2908361], nxt[1000006];
    ll val[1000006], pos[1000006];
    void init(){
        memset(Head, -1, sizeof(Head)); cnt = 0;
    }
    void Insert(ll x, ll v){
        ll key = x % mod;
        pos[cnt] = x, val[cnt] = v, nxt[cnt] = Head[key];
        Head[key] = cnt++;
    }
    ll Find(ll x){
        ll key = x % mod;
        for(ll i = Head[key]; ~i; i = nxt[i]){
            if(pos[i] == x) return val[i];
        }
        return -1ll;
    }
}hs;
thanks!