双哈希

Posted on | In

单哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef unsigned long long ull;
const int N = 100000 + 5;
const ull base = 163;
char s[N];
ull hash[N];
 
void init(){//处理hash值
    p[0] = 1;
    hash[0] = 0;
    int n = strlen(s + 1);
   for(int i = 1; i <=100000; i ++)p[i] =p[i-1] * base;
   for(int i = 1; i <= n; i ++)hash[i] = hash[i - 1] * base + (s[i] - 'a');
}
 
ull get(int l, int r, ull g[]){//取出g里l - r里面的字符串的hash值
    return g[r] - g[l - 1] * p[r - l + 1];
}

和自然溢出法不同的是，这种方法需要取模，并且是两套base mod。每次做哈希操作时，需要两套哈希值都一致，这就大大降低了冲突概率。但是据说常数比较大，并且写起来麻烦一些。

CF1320D

对于一个01串（2e5），给出两种操作：110<->011，可以执行任意多次，q（2e5）个提问，问这个串中某两个子串能否通过这两种操作互相转化。

分析可知，这种操作实际上就是把0左移或右移2位，也就是偶数次，那么如果这两个串中0出现的奇偶序列相同（比如第一个0都是奇数位上，第二个0都是偶数位上）那么就一定能互相转化成功，如果奇偶不同例如某两个0相邻，那是无法彼此转化的。所以问题就变成了，这两个子串中0出现的奇偶序列是否相同，这里是按照奇偶位置分别取1或2，不明白为啥0或1就会wa，，关于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
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;

const int base1=131;
const int base2=13331;
const int mod1=998244353;
const int mod2=1e9+7;
const int maxn=2e5+2;
int pos[maxn],p;
int hsh1[maxn][2],hsh2[maxn][2];
int pow1[maxn],pow2[maxn];
void init_hsh(){
    pow1[0]=pow2[0]=1;
    for(int i=1;i<=p;i++){
        hsh1[i][0]=(1ll*hsh1[i-1][0]*base1+pos[i]%2+1)%mod1;
        hsh1[i][1]=(1ll*hsh1[i-1][1]*base1+!(pos[i]%2)+1)%mod1;
        pow1[i]=1ll*base1*pow1[i-1]%mod1;
        hsh2[i][0]=(1ll*hsh2[i-1][0]*base2+pos[i]%2+1)%mod2;
        hsh2[i][1]=(1ll*hsh2[i-1][1]*base2+!(pos[i]%2)+1)%mod2;
        pow2[i]=1ll*base2*pow2[i-1]%mod2;
    }
}

typedef pair<int,int> pr;
pr gethsh(int l,int r,int st){
    if(st%2){
        return pr((hsh1[r][0]-1ll*pow1[r-l+1]*hsh1[l-1][0]%mod1+mod1)%mod1,(hsh2[r][0]-1ll*hsh2[l-1][0]*pow2[r-l+1]%mod2+mod2)%mod2);
    }else{
        return pr((hsh1[r][1]-1ll*pow1[r-l+1]*hsh1[l-1][1]%mod1+mod1)%mod1,(hsh2[r][1]-1ll*hsh2[l-1][1]*pow2[r-l+1]%mod2+mod2)%mod2);
    }
}
int n;
char s[maxn];
int main(){
    cin>>n;
    cin>>(s+1);
    for(int i=1;i<=n;i++)
        if(s[i]=='0')
            pos[++p]=i;
    init_hsh();
    int q;
    cin>>q;
    int x,y,l;
    while(q--){
        cin>>x>>y>>l;
        int xl=lower_bound(pos,pos+p+1,x)-pos;
        int xr=upper_bound(pos,pos+p+1,x+l-1)-pos-1;
        int yl=lower_bound(pos,pos+p+1,y)-pos;
        int yr=upper_bound(pos,pos+p+1,y+l-1)-pos-1;
        pr px=gethsh(xl,xr,x);
        pr py=gethsh(yl,yr,y);
        cout<<(px==py?"Yes":"No")<<endl;
    }
    return 0;
}
/*
10
0100001001
1
2 9 2
*/