基本思想:
- hash[i]=hash[i-1]*base+s[i].(base:选定的质数,如101,171等)
- 本质:前缀积.
- 对于一个范围l~r,可以利用hash[r]-hash[l]*tmp[r-l+1]获取.(tmp:base的前缀积)
掌握技巧:
- 手动模拟.
#include<cstdio>
#include<iostream>
#include<cstring>
#define ull unsigned long long
using namespace std;
const int MAXN=2e6;
string s;
ull hash_[MAXN],tmp[MAXN];
void initHash(){
int len=s.length();
ull base=101;
tmp[0]=1;
for(int i=1;i<=len;i++){
hash_[i]=hash_[i-1]*base+s[i-1];
tmp[i]=tmp[i-1]*base;
}
}
int main(){
cin>>s;
initHash();
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
ull hash1=hash_[r1]-hash_[l1-1]*tmp[r1-l1+1];
ull hash2=hash_[r2]-hash_[l2-1]*tmp[r2-l2+1];
if(hash1==hash2){
printf("Yes\n");
}else printf("No\n");
}
return 0;
}
菜鸡默默问一句,为什么base要选素数