#include <iostream>
#include <vector>
#include <string>
using namespace std;

class RollingHash {
private:
    static const long long MOD = 1e9 + 7;
    static const long long BASE = 31;
    vector<long long> hash, power;
    
public:
    RollingHash(const string& s) {
        int n = s.length();
        hash.resize(n + 1);
        power.resize(n + 1);
        
        power[0] = 1;
        for (int i = 1; i <= n; i++) {
            power[i] = (power[i-1] * BASE) % MOD;
        }
        
        hash[0] = 0;
        for (int i = 1; i <= n; i++) {
            hash[i] = (hash[i-1] * BASE + (s[i-1] - 'a' + 1)) % MOD;
        }
    }
    
    long long getHash(int l, int r) { // 0-indexed, inclusive
        l++; r++; // Convert to 1-indexed
        long long result = hash[r] - (hash[l-1] * power[r-l+1]) % MOD;
        return (result % MOD + MOD) % MOD;
    }
    
    bool areEqual(int l1, int r1, int l2, int r2) {
        return getHash(l1, r1) == getHash(l2, r2);
    }
};

int main() {
    string s = "abacaba";
    RollingHash rh(s);
    
    cout << "String: " << s << endl;
    
    // Check if substrings are equal
    cout << "s[0:2] == s[4:6]: " << rh.areEqual(0, 2, 4, 6) << endl; // "aba" == "aba"
    cout << "s[0:1] == s[3:4]: " << rh.areEqual(0, 1, 3, 4) << endl; // "ab" == "ca"
    cout << "s[1:3] == s[5:6]: " << rh.areEqual(1, 3, 5, 6) << endl; // "bac" == "ba"
    
    // Get hash values
    cout << "Hash of s[0:2]: " << rh.getHash(0, 2) << endl;
    cout << "Hash of s[4:6]: " << rh.getHash(4, 6) << endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class DoubleHash {
private:
    static const long long MOD1 = 1e9 + 7;
    static const long long MOD2 = 1e9 + 9;
    static const long long BASE1 = 31;
    static const long long BASE2 = 37;
    
    vector<long long> hash1, hash2, power1, power2;
    
public:
    DoubleHash(const string& s) {
        int n = s.length();
        hash1.resize(n + 1);
        hash2.resize(n + 1);
        power1.resize(n + 1);
        power2.resize(n + 1);
        
        power1[0] = power2[0] = 1;
        for (int i = 1; i <= n; i++) {
            power1[i] = (power1[i-1] * BASE1) % MOD1;
            power2[i] = (power2[i-1] * BASE2) % MOD2;
        }
        
        hash1[0] = hash2[0] = 0;
        for (int i = 1; i <= n; i++) {
            int c = s[i-1] - 'a' + 1;
            hash1[i] = (hash1[i-1] * BASE1 + c) % MOD1;
            hash2[i] = (hash2[i-1] * BASE2 + c) % MOD2;
        }
    }
    
    pair<long long, long long> getHash(int l, int r) {
        l++; r++;
        long long h1 = hash1[r] - (hash1[l-1] * power1[r-l+1]) % MOD1;
        long long h2 = hash2[r] - (hash2[l-1] * power2[r-l+1]) % MOD2;
        h1 = (h1 % MOD1 + MOD1) % MOD1;
        h2 = (h2 % MOD2 + MOD2) % MOD2;
        return {h1, h2};
    }
    
    bool areEqual(int l1, int r1, int l2, int r2) {
        return getHash(l1, r1) == getHash(l2, r2);
    }
};

int main() {
    string s = "programming";
    DoubleHash dh(s);
    
    cout << "String: " << s << endl;
    
    auto h1 = dh.getHash(0, 3); // "prog"
    auto h2 = dh.getHash(7, 10); // "ming"
    
    cout << "Hash of 'prog': (" << h1.first << ", " << h1.second << ")" << endl;
    cout << "Hash of 'ming': (" << h2.first << ", " << h2.second << ")" << endl;
    
    cout << "Are 'prog' and 'ming' equal: " << dh.areEqual(0, 3, 7, 10) << endl;
    cout << "Are 'prog' and 'prog' equal: " << dh.areEqual(0, 3, 0, 3) << endl;
    
    return 0;
}