字符串哈希

字符串哈希：

我们可以把一个字符串哈希处理成一个数字。

具体做法：

将字符串看作是一个p进制数(p大于字符的ascii码值)，acbd哈希成数字是：(a*p^3 + c*p^2 + b*p^1 + d*p^0)modQ，p一般取131或者13331，Q取2e64时，一般不会出现哈希冲突。
 

用法：

对于一个字符串来说，我们可以利用字符串哈希处理出每个字符的前缀哈希，这样的话我们就可以在O(1)的复杂度下求出出任意子串的哈希值。我们要求字符串l~r范围子串的哈希值的话，求s[l-1]*p^(r-l+1)-s[r]即可。

例题：

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1]和 [l2,r2]这两个区间所包含的字符串子串是否完全相同。

我们预处理出每个字符的前缀哈希，可以在O(1)的时间复杂化度下对比两个子串是否相同。

我们使用unsigned long long 来存前缀哈希的话，越界就相当于取模2e64。

代码如下：

#include<iostream>
using namespace std;
const int N=1e5+10;
unsigned long long h[N],p[N];//哈希值和进制数（取2e64的结果）

unsigned long long get(int l,int r){
    return h[r]-h[l-1]*p[r+1-l];
}

int main(){
    int n,m;
    cin>>n>>m;
    char c[N];
    scanf("%s",c+1);//从第一位开始读
    p[0]=1;//相差0位乘1
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]*131;//自动取模
        h[i]=h[i-1]*131+c[i];//自动取模
    }
    int l1,r1,l2,r2;
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))puts("Yes");
        else puts("No");
    }
    return 0;
}