AcWing 841. 字符串哈希
原题链接
简单
作者:
LBAC
,
2024-02-25 18:22:05
,
所有人可见
,
阅读 19
哈希字符串
// 哈希字符串核心思想:从p进制的角度将一个字符串看成一个数字
#include<iostream>
#include<string>
using namespace std;
typedef unsigned long long ULL; //unsigned long long的表示范围即为0~2^64,当溢出时为自动回到0,因此就当于对Q取模
const int N = 1e5+5,P = 131;//// P = 131 或 13331 并且 Q=2^64,在99%的情况下不会出现冲突
ULL h[N],p[N]; //这个p[N]数组 是装的P有多少次方
// h[i]前i个字符的hash值
// 字符串变成一个p进制数字,体现了字符+顺序,需要确保不同的字符串对应不同的数字
ULL query(int l,int r){
return h[r] - h[l-1]*p[r-l+1]; //将位数较少的哈希字符串乘于一个p^(r-l+1)次方,使得两个哈希字符串位数相同,进而可以进行相减
}
int main(){
int n,m;
cin>>n>>m;
string s;
cin>>s;
//字符串从1开始编号,h[1]为前一个字符的哈希值
p[0] = 1; // p^0 = 1
h[0] = 0;
for(int i=0;i<n;i++){
p[i+1] = p[i]*P; //p[N]数组 是装的P有多少次方
h[i+1] = h[i]*P + s[i]; //给字符赋予哈希值,此处不用取模
}
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(query(l1,r1) == query(l2,r2)) printf("Yes\n"); //如果两个子串的哈希值相同则子串相同
else printf("No\n");
}
return 0;
}