AcWing 841. 贴一个string读入的C++代码
原题链接
简单
作者:
杨大鑫_ωノ
,
2021-05-28 22:07:08
,
所有人可见
,
阅读 377
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 +10, P = 131;
int n, m;
ULL h[N], p[N];
ULL get_hash(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
string s;
cin >> s;
p[0] = 1;
for(int i = 0; i < n; i++)
{
p[i + 1] = p[i] * P;
h[i + 1] = h[i] * P + s[i];//这里求前缀和,对字符串很不友好。
//前缀和需要从1开始,但是这里字符串是从0开始,所以这里就开始映射了。
}
while(m--)
{
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if(get_hash(l1, r1) == get_hash(l2, r2)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}