138. 兔子与兔子【字符串哈希】

很基础的字符串哈希

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
const int N=1e6+10;
const int M=233;
ull base[N],h[N],n;
string s;
void init()
{
    base[0]=1;
    for(int i=1;i<N;i++) base[i]=base[i-1]*M;
}
ull get(int l,int r)//获取字符串[l,r]的哈希值
{
    return h[r]-h[l-1]*base[r-l+1];
}
int main(void)
{
    cin>>s;
    s="0"+s;
    init();
    for(int i=1;i<s.size();i++) h[i]=h[i-1]*M+s[i]-'a';
    cin>>n;
    while(n--)
    {
        int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2;
        ull sum1=get(l1,r1);
        ull sum2=get(l2,r2);
        if(sum1==sum2) puts("Yes");
        else puts("No");
    }
    return 0;
}