哈希表 AcWing 841. 字符串哈希

原题链接

AcWing 841. 字符串哈希

算法标签

字符串哈希 哈希

思路

模拟举例

则对应字符串hash

求hash
把对应字符串看作一段p进制数

注意 ：不能将字符映射为0
原因 ：若将A映射为0， 则会导致所有AA, AAA, ……将都为0。

冲突处理
对于数据范围 < 2^64数据 ，P一般取131或13331，可保证hash冲突概率<0.01%

代码

#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为字符串映射对应hash值 
//对于数据范围 < 2^64数据 
//P一般取131或13331
//这样可保证hash冲突概率<0.01% 
const int N = 100005, P = 131;
// h存储字符串前缀对应hash值 p存储该位进制数
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);
}
// 对应字符串hash值
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);
    // 从1开始映射
    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;
}

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈