字符串前缀哈希法
一定注意从1开始存!!!
str=”ABCABCABC”
h[1]=”A”的哈希值
h[2]=”AB”
h[3]=”ABC”
h[4]=”ABCA”
把字符串看成一个p进制的数
“ABCD”
=(1234)p
=(1p^3+2p^2+3p^1+4p^0) mod Q
把字符串转化为数字
再取模来转化为一个比较小的数字
即映射到0~Q-1的位置
注意
1 不能映射成0
(eg A->0 AA->0 重复了)
2 不考虑冲突的情况
p取131或13331 Q取2^64时 可假定不存在冲突
用途:利用前缀哈希 可以计算出所有字串的哈希值
例:求L~R的哈希值
已知
h[R](1~R的哈希值)
和h[L-1](1~L-1的哈希值)h[R]:R是第0位 1是R-1位 p^(R-1)~p^0
h[L-1]: L-1是第0位 1是L-2位
p^(L-2)~p^0做法:
1 把h[L-1]往左移 直到与h[R]对齐(左端对齐 )
h[L-1]p^(R-L+1)
2 用h[R]-这个数
h[R]-h[L-1]p^(R-L+1)
即为L~R的哈希值
技巧 用unsigned long long(无符号整数) 来存h
这样就不需要取模了
因为本身会溢出 所以相当于取模
预处理
h[i]=h[i-1]*p+str[i];
代码实现
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10,Q=131;
typedef unsigned long long ULL;
ULL h[N],p[N];
ULL query(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
int n,m;
cin>>n>>m;
char a[N];
cin>>a+1;//注意从一开始存!!!
p[0]=1;//别忘了p的0次方是1
for(int i=1;i<=n;i++){
h[i]=h[i-1]*Q+a[i];
p[i]=p[i-1]*Q;//p[k]存Q的k次方
}
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(query(l1,r1)==query(l2,r2)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}