字符串哈希表
字符串哈希 841. 自己看看
解法
字符串哈希前缀法
- 将字符串看成p进制的数
- 不能映射成0,在p=131或13331,Q=2^64是不存在冲突的经验值
算法1
代码很简单,但是理解起来比较麻烦,可以先用二进制进行字母排列来理解,然后用y总说的p来算就行了。
C++ 代码
#include<iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5+10,P=131;
int n,m;
char str[N];
ULL h[N],p[N];
//h数组表示前缀的哈希值
ULL get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];//计算l到r中p进制的值
}
int main()
{
cin>>n>>m>>str+1;
p[0]=1;//p的0次方是1
for(int i=1;i<=n;i++)
{
p[i]=p[i-1]*P;//每往后一位,乘一个P
h[i]=h[i-1]*P+str[i];//
}
while(m--)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(get(l1,r1)==get(l2,r2))puts("Yes");
else puts("No");
}
return 0;
}