基础

一般哈希

直接用map

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

双哈希

开两个哈希，不用自然溢出，用取模，mod1=1e9+7,mod2=1e9+11;

P=131 or 13331

1
2
3
4
5
6
7
8
9
ull get1(int l,int r){
    return (hs1[r]-hs1[l-1]*peac1[r-l+1]%mod1+mod1)%mod1;//一定要去两次mod取正数
}
ull get2(int l,int r){
    return (hs2[r]-hs2[l-1]*peac2[r-l+1]%mod2+mod2)%mod2;    
} 
pll get(int l,int r){
    return {get1(l,r),get2(l,r)};
}

集合哈希

见下文例题

Birthday Cake

题意

给定n个串，求有多少对串能拼出平方串（能够表示成两个相同的字符串连接在一起的，即A+A ）

思考

首先，有一个结论若A+B是平方串，那么B+A也是平方串，所以只要正着做一次就行了。

if(字符串前后缀相同) 就检查去掉前后缀之后的字符串出现过几次ans+=这个次数；
举个栗子： cabc 这个字符串前后缀 c 相同 就看ab出现过几次 ab和cabc就可以组成abcabc；

代码

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
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define ull unsigned long long 
#define pll pair<ull,ull>
const int maxn=4e5+5;
ull hs1[maxn],hs2[maxn],pec=131,peac1[maxn],peac2[maxn];
ull mod1=1e9+7,mod2=1e9+11;
pll res[maxn];
map<pll, ull> cnt;
ull get1(int l,int r){
    return (hs1[r]-hs1[l-1]*peac1[r-l+1]%mod1+mod1)%mod1;//一定要去两次mod
}
ull get2(int l,int r){
    return (hs2[r]-hs2[l-1]*peac2[r-l+1]%mod2+mod2)%mod2;    
} 
pll get(int l,int r){
    return {get1(l,r),get2(l,r)};
}
int id=0;
int main(){
    peac1[0]=1;
    peac2[0]=1;//初始化进制
    for(int i=1;i<maxn;i++) peac1[i]=peac1[i-1]*pec%mod1;
    for(int i=1;i<maxn;i++) peac2[i]=peac2[i-1]*pec%mod2;
    int n;
    cin>>n;
    while(n--){
        char s[maxn];
        cin>>s+1;
        int len=strlen(s+1);
        for(int i=1;i<=len;i++){
            hs1[i]=(hs1[i-1]*pec%mod1+(s[i]-'a'+1))%mod1;
            hs2[i]=(hs2[i-1]*pec%mod2+(s[i]-'a'+1))%mod2;
        }    
        cnt[{hs1[len],hs2[len]}]++;//记录出现的字符串双哈希
        for(int i=1;i+i<len;i++){
            if(get(1,i)==get(len-i+1,len)){ //前后缀双哈希值相等
                res[++id]=get(i+1,len-i); //存入res数组
            } 
        }
    }
    ull ans=0;
    for(int i=1;i<=id;i++) {  //ans+=出现次数即为所得
        ans+=cnt[res[i]];
    }
    for(auto it : cnt) ans += it.second * (it.second - 1) / 2;
    //如果是相同的字符串就可以组成（（n-1）*n）/2个答案
    cout<<ans<<'\n';
}

E - Prefix Equality

题意

两个序列A,B。q次询问，每次询问给出x,y，判断序列A的前x个数的集合与序列B的前y个数的集合是否相等。

思考

哈希

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef unsigned long long ULL;
int pow=131;
int n,q,x,y;
int a,b;
ULL aa[200010],bb[200010];
map<int,int> mp;
set<int> st;
int get(int u){
    if(mp[u]) return mp[u];
    else return mp[u]=rand()%(1000000000+7);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        aa[i]=aa[i-1];
        scanf("%d",&a);
        if(!st.count(a)){
            aa[i]+=get(a);
            st.insert(a);
        }
    }
    st.clear();
    for(int i=1;i<=n;i++){
        bb[i]=bb[i-1];
        scanf("%d",&b);

        if(!st.count(b)){
            bb[i]+=get(b);
            st.insert(b);
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&x,&y);
        if(aa[x]==bb[y])
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}