23.hash

原题链接

字符哈希串的意思：其实就是将字符串的前缀转换为数来存值
由于每位的权值是不一样的 所以每个前缀值都对应着唯一的一种字符串

所以相减后的值也应该是唯一的 从而利用相减后的值可以判断字符串的区间段是否相等

注意点：

• 由于前缀值的值会很大 所以应该将数组中的数据定义为ULL型
  typedef unsigned long long ULL;

• P为权重，131为经验值 即P=131或13331时 哈希冲突的可能性最小

• ULL h[N]; //h[]存放字符串的前缀值
  ULL p[N]; //p[]存放各个位数的相应权值

• 将h[l-1]左移，其目的事实上是为了将h[l-1]的高位与h[r]的高位相对齐从而完成计算

• p[0]的权值必须赋值为1 ，字符串下标必须从1开始

再是计算公式：

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
typedef unsigned long long ULL;

const int N=1e5+10,P=131;
char str[N];
int n,m;
ULL h[N],p[N];

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

int main()
{
    cin>>n>>m;
    scanf("%s",str+1);//字符串下标从1开始
    
    p[0]=1;//0的任何进制都是1
    
    for(int i=1;i<=n;i++)//求出字符串长度的所有hash值
    {
        p[i]=p[i-1]*P;//每一位所表示的进制
        h[i]=h[i-1]*P+str[i];//每一位的hash值
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1)==get(l2,r2))
        {
            cout<<"Yes"<<endl;
        }
        else
            cout<<"No"<<endl;
    }
    return 0;
}