Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <fstream>
- #include <iostream>
- #include <unordered_set>
- #include <random>
- unsigned long long h[100001], deg[100001];
- void makeHash(std::string s, int n, unsigned long long P) {
- h[0] = 0;
- deg[0] = 1;
- for (int i = 0; i < n; i++) {
- h[i + 1] = h[i] * P + s[i];
- deg[i + 1] = deg[i] * P;
- }
- }
- unsigned long long getHash(const std::string&, int st, int end) {
- return h[end] - h[st] * deg[end - st];
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(0);
- std::random_device rd;
- std::mt19937 gen(rd());
- std::uniform_int_distribution<long long int> distr(INTMAX_MAX, UINTMAX_MAX);
- const unsigned long long P = distr(gen);
- int M;
- std::string str;
- std::cin >> str >> M;
- makeHash(str, str.size(), P);
- for (int i = 0; i < M; i++) {
- int a, b, c, d;
- std::cin >> a >> b >> c >> d;
- if (((b - a) == (d - c)) && getHash(str.substr(a - 1, b - a + 1), a - 1, b) == getHash(str.substr(c - 1, d - c + 1), c - 1, d)) std::cout << "Yes\n";
- else std::cout << "No\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement