[数据结构与算法]?数据结构?——字符串哈希表

字符串哈希

简介

字符串哈希表全称前缀哈希表，将字符串通过hash函数变成一个p进制的数，使不同的字符串映射到不同的数字上。例如：ABCD字符串，公式为

注意点

1. 任何字符都不能映射成0，否则会出现不同的字符串都映射到0的情况。例如：“A”,"AA"等。

2. 冲突：关于字符串哈希的方式，前人找到如果将P设为131或者13331，Q取2（64），产生冲突的概率及其小，大概十几亿分之一，这里我们认为我们人品足够好，比赛时不会产生冲突

步骤

1. 用公式存放每一个字符串的hash值

2. 前缀和公式来比较两段字符串是否相等， h[i+1]=h[i]×P+s[i]h[i+1]=h[i]×P+s[i] i∈[0,n?1]i∈[0,n?1]。h为每个字符的hash值，s[i]表示字符数组。

两个重要的公式

?

区间和公式的理解：

ABDCE 与 ABC 的前三个字符值相同，现在要求h[3,5] = h[5] - h[3]*p(r-l+1) ，意思是差两位就给左边的乘上P（2） 把ABC进位两位 ， 可以理解为变成了ABCDE-ABC00就能求出DE的哈希值了

代码

AcWing 841. 字符串哈希

#include<iostream>
?#include<cstdio>
?#include<string>
?using namespace std;
?typedef unsigned long long ULL;
?const int N = 1e5+5,P = 131;//131 13331
?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;
? ? ?string x;
? ? ?cin>>x;
??
? ? ?p[0] = 1;
? ? ?h[0] = 0;
? ? ?for(int i=0;i<n;i++){
? ? ? ? ?p[i+1] = p[i]*P; ? ? ? ? ? ?
? ? ? ? ?h[i+1] = h[i]*P +x[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;
?}
??

?