rt,样例没过,调的有点红温。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
string s;
int bas1 = 114, bas2 = 514, mod1 = 1e18 - 11, mod2 = 998244353;
int hsh1[N], hsh2[N];
int sba1[N], sba2[N];
// sum of bas 1/2
int mul1(int a, int b)
{
int ans = 1;
while(b)
{
if(b & 1) ans = ans * a % mod1;
a = a * a % mod1;
b >>= 1;
}
return ans;
}
int mul2(int a, int b)
{
int ans = 1;
while(b)
{
if(b & 1) ans = ans * a % mod2;
a = a * a % mod2;
b >>= 1;
}
return ans;
}
signed main()
{
cin >> s;
int len = s.size();
s = "!" + s;
sba1[0] = sba2[0] = 1;
for(int i = 1; i <= len; i++)
{
hsh1[i] = (hsh1[i - 1] * bas1 % mod1 + s[i]) % mod1;
hsh2[i] = (hsh2[i - 1] * bas2 % mod2 + s[i]) % mod2;
sba1[i] = sba1[i - 1] * bas1 % mod1;
sba2[i] = sba2[i - 1] * bas2 % mod2;
// cout << hsh1[i] << " " << hsh2[i] << endl;
}
int q;
cin >> q;
while(q--)
{
int l1, l2, r1, r2;
scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
bool f1=((hsh1[r1]-mul1(hsh1[l1-1], sba1[r1 - l1 + 1]) + mod1) % mod1 == (hsh1[r2]-mul1(hsh1[l2 - 1], sba1[r2 - l2 + 1]) + mod1) % mod1);
bool f2=((hsh2[r1]-mul2(hsh2[l1-1], sba2[r1 - l1 + 1]) + mod2) % mod2 == (hsh2[r2]-mul2(hsh2[l2 - 1], sba2[r2 - l2 + 1]) + mod2) % mod2);
// cout << (hsh1[r1]-mul1(hsh1[l1-1], sba1[r1 - l1 + 1]) + mod1) % mod1 << " " << (hsh1[r2]-mul1(hsh1[l2 - 1], sba1[r2 - l2 + 1]) + mod1) % mod1 << " " << (hsh2[r1]-mul2(hsh2[l1-1], sba2[r1 - l1 + 1]) + mod2) % mod2 << " " << (hsh2[r2]-mul2(hsh2[l2 - 1], sba2[r2 - l2 + 1]) + mod2) % mod2 << endl;
if(f1 && f2) printf("Yes\n");
else printf("No\n");
}
return 0;
}
/*
148,818,971
*/