Acwing题解系列——841. 字符串哈希

#include<iostream>
using namespace std;
const int N=100010;
const int P=131;
/* 题解 https://www.acwing.com/solution/content/24738/ 可以 
把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。
采用字符的ascii 码乘上 P 的次方来计算哈希值。
X1X2X3...Xn字符串  
映射公式 (X1×Pn-1次方+X2×Pn-2次方+?+Xn?1×P1+Xn×P0次方)modQ
注意点：
1. 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
2. 冲突问题：通过巧妙设置P (131 或 13331) , Q (2^64)一般可以理解为不产生冲突。

问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和。
*/
char str[N];
typedef unsigned long long ULL;//最大到2^64 
ULL h[N],p[N];
//ULL是他们的值 好多次方所以可能爆int h[i]是前i个字符的hash值
//p[i]就是p的i次方
ULL get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    int n,m;
    scanf("%d%d%s",&n,&m,str);//如果用str+1 使得字符串从1开始
    //用string类的话 就要i从0到n-1那一套 
    p[0]=1;
    h[0]=0;
    for(int i=0;i<n;i++){//str+1就要从1到n 
        p[i+1]=p[i]*P;//p[i]=p[i-1]*P
        h[i+1]=h[i]*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)) printf("Yes\n");
        else printf("No\n"); 
    }
    return 0;
}