- 【模板】字符串哈希
1
- @ 2026-7-22 11:10:18
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
template<int B, int mod>
struct Hash {
// int B = 133331, mod = 1e9 + 7;
vector<ll> h, p;
Hash(string s) {
int n = s.size();
h.resize(n); p.assign(n, 1);
h[0] = s[0];
for (int i = 1; i < n; i++) {
h[i] = h[i-1] * B + s[i];
h[i]%=mod;
p[i] = p[i - 1] * B % mod;
}
}
ll get(int l, int r) {
ll H = h[r] - h[l - 1] * p[(r - l + 1)];
return (H % mod + mod) % mod;
}
};
void solve() {
int n, m;
cin >> n >> m;
string s; cin >> s;
s = ' ' + s;
Hash<133331, (int)1e9 + 7> hash1(s);
Hash<1333331, (int)998244353> hash2(s);
while (m--) {
int l, r, x, y;
cin >> l >> r >> x >> y;
cout << (hash1.get(l, r) == hash1.get(x, y) && hash2.get(l, r) == hash2.get(x, y) ? "Yes" : "No") << '\n';
}
}
signed main() {
// long double p = 1e18;
// cout << powl(1 - 1 / p, 2e6) << '\n';
int t = 1;
while (t--) solve();
return 0;
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/
0 条评论
目前还没有评论...
信息
- ID
- 498
- 时间
- ms
- 内存
- MiB
- 难度
- 5
- 标签
- 递交数
- 128
- 已通过
- 48
- 上传者