[Acwing]AcWing 841. 字符串哈希

算法标签 哈希,字符串哈希

题目简叙

思路

依据经验，我们使得数值尽量重复时需要限定:
1.p最好是131或者13331
2.对数值%(₂26)，我们刚好采取unsigned long long 溢出时的状态也是一致的
这样几乎没有可能重复从而冲突

将字符串的前缀转换为数来存值
由于每位的权值是不一样的 所以每个前缀值都对应着唯一的一种字符串
所以相减后的值也应该是唯一的 从而利用相减后的值可以判断字符串的区间段是否相等

字符串
str="ABCD"

字符串前缀对应
h[1]="A"
h[2]="AB"
h[3]="ABC"
h[4]="ABCD"

我们求h[4]对应的值
相当于
h[4]=（"A,B,C,D"）
target=("A"*P^3+"B"*P^2+"C"*P^1+"D"*P)MOD(Q) //Q==2^26==unsigned long long

我们求一段范围内的值
--------|-----------|---
		L			R
R-1					0
       L-1
L-2     0 	

我们将h[l-1]左移，使得h[l-1]的高位与h[r]相对齐
从而进行计算

return h[r]-h[l-1]*p[r-l+1]; 
//如果返回的对应的哈希值相等，就表明相同

代码

#include<iostream>
#include<string>

using namespace std;

int l1,r1,l2,r2;

const int N = 1e5+10;
const int P = 131;
typedef long long ULL;
ULL h[N];//h[]存放字符串的前缀值
ULL p[N];//p[]存放各个位数的相应权值
char str[N];

int get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1]; //求一段的值
}

int main(){
    int n,m;
    cin>>n>>m;
    
    cin>>str+1;
    
    p[0]=1;//初始化
    for(int i=1;i<=n;i++)
        h[i]=h[i-1]*P+str[i],p[i]=p[i-1]*P;//前缀和与对应的P
        
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        get(l1,r1)==get(l2,r2)?puts("Yes"):puts("No");//如果对应的哈希值相等，就表明相同
    }
    return 0;
}

AC记录