Hasing_0_based.cpp

const int N = 1e6 + 9;

int power(long long n, long long k, const int mod)
{
    int ans = 1 % mod;
    n %= mod;
    if (n < 0)
        n += mod;
    while (k)
    {
        if (k & 1)
            ans = (long long)ans * n % mod;
        n = (long long)n * n % mod;
        k >>= 1;
    }
    return ans;
}

const int MOD1 = 127657753, MOD2 = 987654319;
const int p1 = 137, p2 = 277;
int ip1, ip2;
pair<int, int> pw[N], ipw[N];

void prec()
{
    pw[0] = {1, 1};
    for (int i = 1; i < N; i++)
    {
        pw[i].first = 1LL * pw[i - 1].first * p1 % MOD1;
        pw[i].second = 1LL * pw[i - 1].second * p2 % MOD2;
    }
    ip1 = power(p1, MOD1 - 2, MOD1);
    ip2 = power(p2, MOD2 - 2, MOD2);
    ipw[0] = {1, 1};
    for (int i = 1; i < N; i++)
    {
        ipw[i].first = 1LL * ipw[i - 1].first * ip1 % MOD1;
        ipw[i].second = 1LL * ipw[i - 1].second * ip2 % MOD2;
    }
}

struct Hashing
{
    int n;
    string s;                  // 0-indexed
    vector<pair<int, int>> hs; // prefix hashes: hs[i] = hash of s[0..i-1]

    Hashing() {}
    Hashing(const string &_s)
    {
        n = _s.size();
        s = _s;
        hs.resize(n + 1); // hs[0] = 0
        hs[0] = {0, 0};
        for (int i = 0; i < n; i++)
        {
            hs[i + 1].first = (hs[i].first + 1LL * s[i] * pw[i].first % MOD1) % MOD1;
            hs[i + 1].second = (hs[i].second + 1LL * s[i] * pw[i].second % MOD2) % MOD2;
        }
    }

    // get hash of substring [l, r] (0-based, inclusive)
    pair<int, int> get_hash(int l, int r)
    {
        assert(0 <= l && l <= r && r < n);
        pair<int, int> ans;
        ans.first = (hs[r + 1].first - hs[l].first + MOD1) % MOD1;
        ans.first = 1LL * ans.first * ipw[l].first % MOD1;
        ans.second = (hs[r + 1].second - hs[l].second + MOD2) % MOD2;
        ans.second = 1LL * ans.second * ipw[l].second % MOD2;
        return ans;
    }

    // pair<int, int> get_full_hash() const
    // {
    //     return get_hash(0, n - 1);
    // }
};