题目描述

字符串哈希

字符串前缀哈希法

用数字代替字符串，当数字相等时则字符串也相等

h[N]表示前N个字符的哈希值，最后通过取模(mod q)，将字符串的哈希值映射到0~q-1上

（1）字符的哈希值不能映射为0
（2）在假定不会发生冲突的情况下，一般设P=131或13331;则Q=2^64

为啥两段那样减了一下就相等了：（比较学术性的解释）
余数的差等于差的余数，意思是：a%p - b%p = (a-b)%p，所以：1234567%P - 1230000%P = 4567%P
（其实自己画画就很明显）

C++ 代码

#include<iostream>
using namespace std;
const int N=100010;
typedef unsigned long long ULL;        //一种类型，遇到范围是2^63，取模2^64的，防止溢出
char str[N];                    //存储字符串
ULL p[N],h[N],P=131;//p[N]存储p的几次方 h[N]表示前N个字符的哈希值,换一种类型就不用取模了，因为多出来的溢出了


ULL get(int l,int r)     //已知1~R的哈希值和1~L-1的哈希值，求L~R的哈希值 左边是高位，右边是低位
{
    //R-1-(L-2)(L-1和R相差的位数)
    //因为h[l-1]是比h[r]的长度短的，所以照左边是高位，则要将h[l-1]*相差的位数才能将其左移到和h[R]一样的位置
    return h[r]-h[l-1]*p[r-l+1];     //剩下的数字即为从L~R的哈希值
}
int main()
{
    int n,m;
    cin>>n>>m;
    //用指针的方法输入一个字符串如果直接用scanf("%s",str);的话，就会出现一个问题：scanf函数遇到空格或TAB，就会停下来。所以用指针的方式就可以防止这种情况发生。

    scanf("%s",str+1);   //从str[1]开始赋值

    p[0]=1;             //不能映射为0
    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;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}