Hashtable AcWing 841. String hash

Original link

AcWing 841. String hash

Algorithm tags

String hash Hash

Ideas

Simulation example

Then the corresponding string hash

seek hash
Treat the corresponding string as a segment p Hexadecimal number

Be careful ： Characters cannot be mapped to 0
reason ： If the A It maps to 0, Will cause all AA, AAA, …… Will all be 0.

Conflict handling
For data range < 2^64 data ,P Usually take 131 or 13331, warrantable hash Probability of conflict <0.01%

Code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
// P Map the corresponding string hash value  
// For data range  < 2^64 data  
//P Usually take 131 or 13331
// This ensures that hash Probability of conflict <0.01% 
const int N = 100005, P = 131;
// h The storage string prefix corresponds to hash value  p Store the decimal number 
ull h[N], p[N];
char s[100005];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
//  Corresponding string hash value 
ull get(int l, int r){
    return h[r]-h[l-1]*p[r-l+1];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=read(), m=read();
    scanf("%s", s+1);
    //  from 1 Start mapping 
    p[0]=1;
    rep(i, 1, n+1){
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+s[i];
    }
    while(m--){
        int l1=read(), r1=read(), l2=read(), r2=read();
        if(get(l1, r1)!=get(l2, r2)){
            puts("No");
        }else{
            puts("Yes");   
        }
    }
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support