P10468 兔子与兔子（Hash）

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int p = 1e9+7,base = 131;
const int p2 = 1e9+9,base2 = 13331;
const int N = 1000010;
ll c[N],h[N];//c存base的i次幂,h存hash值
ll c2[N],h2[N];
ll _hash(int l,int r)
{
	//注意此处减去的是h[l-1]
	return (h[r] - h[l-1]*c[r-l+1]%p + p)% p;
}
ll _hash2(int l,int r)
{
	//注意此处减去的是h[l-1]
	return (h2[r] - h2[l-1]*c2[r-l+1]%p2 + p2)% p2;
}
bool check(int l1,int r1,int l2,int r2)
{
	return _hash(l1,r1)==_hash(l2,r2)&&_hash2(l1,r1)==_hash2(l2,r2);
}
void init(string &a)
{
	int n = a.size();
	a = " "+a;
	c[0] = 1;c2[0] = 1;
	
	//注意此处字符串hash时不应该加a[i]-'a'，若遇到全a串则全为0
	for(int i=1;i<=n;++i) c[i] = c[i-1]*base%p;
	for(int i=1;i<=n;++i) h[i] = (h[i-1]*base+a[i])%p;	
	for(int i=1;i<=n;++i) c2[i] = c2[i-1]*base2%p2;
	for(int i=1;i<=n;++i) h2[i] = (h2[i-1]*base2+a[i])%p2;
}
void solve()
{
	string s;
	cin>>s;
	init(s);
	int m;
	cin>>m;
	while(m--)
	{
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		
		if(check(l1,r1,l2,r2)) cout<<"Yes\n";
		else cout<<"No\n";
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}