字符串hash
作者:
无知_5
,
2022-04-03 15:58:10
,
所有人可见
,
阅读 178
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int N = 1e6 + 10, p = 131;
ull prefix[N];
char s[N];
ull pw[N];
ull gethash(int l, int r)
{
return prefix[r] - prefix[l-1] * pw[r-l+1];
}
int main()
{
scanf("%s", s + 1);
int size = strlen(s+1);
pw[0] = 1;
for (int i = 1; i <= size; i++)
{
prefix[i] = prefix[i-1] * p + s[i] - 'a';
pw[i] = pw[i-1] * p;
}
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int l1,r1,l2,r2;
cin >> l1 >> r1 >> l2 >> r2;
if(gethash(l1,r1) == gethash(l2,r2))
printf("Yes\n");
else
printf("No\n");
}
}