Rolling Hash C++ Implementation

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

// computes a^b in O(log b)
long long fast_pow(long long a, int p, long long MOD)
{
  if(p == 0) return 1;
  long long half = fast_pow(a, p/2, MOD);
  if(p%2 == 0) return half * half % MOD;
  return a * half % MOD * half % MOD;
}

// compute inverse_mod(n, MOD) in O(log MOD)
long long inverse_mod(long long n, long long MOD){ return  fast_pow(n, MOD - 2, MOD); }

struct rolling_hash
{
    long long p;
    long long M;
    vector<long long> P;
    vector<long long> Pinv;
    vector<long long> h;

    // returns a vector of size n where P[i] = p^a
    vector<long long> prepare_P(long long p, long long M, int n)
    {
        P.assign(n, 0);
        P[0] = 1;
        for(int i=1;i<n;i++) P[i] = P[i-1] * p % M;
        return P;
    }

    // returns a vector of size n where Pinv[i] = inverse_mod(p^a, M)
    vector<long long> prepare_Pinv(long long p, long long M, int n)
    {
        Pinv.assign(n+1, 0);
        for(int a=0;a<n;a++) Pinv[a] = inverse_mod(fast_pow(p, a, M), M);
        return Pinv;
    }

    // instatiates a rolling hash by computing P, Pinv, and the total hash
    rolling_hash(long long p, long long M, string s)
    {
        this->p = p;
        this->M = M;
        prepare_P(p, M, s.size());
        prepare_Pinv(p, M, s.size());

        h.assign(s.size(), 0);
        for(int i=0;i<s.size();i++)
        {
            if(i!=0) h[i] = h[i-1];
            h[i] = (h[i] + (s[i] * P[i]) % M) % M;
        }
    }

    // returns hash(s[a...b]) in O(1)
    long long hash_fast(int L, int R)
    {
        if(L==0) return h[R];
        int ans = 0;
        ans = ((h[R] - h[L-1]) % M + M) % M;
        ans = ans * Pinv[L] % M;
        return ans;
    }
};

// use this for unordered_set if you need more than 1 hash
struct pair_hash
{
    template <class T1, class T2>
    size_t operator () (pair<T1, T2> const& pair) const
    {
        size_t h1 = hash<T1>()(pair.first);
        size_t h2 = hash<T2>()(pair.second);

        return h1 ^ h2;
    }
};

// computes the hash of a string in O(n)
long long compute_hash(string& s) {
    int p = 31;
    int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + c * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

int main()
{
    string s = "supercallifragilisticexpialidocious";
    int n = s.size();
    rolling_hash rh1(31, 1e9+9, s);

    int tests_passed = 0;
    int tests = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            string sub = s.substr(i, j - i + 1);
            int fast_hash = rh1.hash_fast(i, j);
            int slow_hash = compute_hash(sub);
            cout << "Hashing substring: " << sub << '\n';
            cout << "Slow substring hash O(n) found: " << slow_hash << '\n';
            cout << "Fast substring hash O(1) found: " << fast_hash << '\n';
            if (slow_hash == fast_hash)
            {
                tests_passed++;
                cout << "passed\n\n";
            }
            else
                cout << "failed\n\n";
            tests++;
        }
    }

    cout << tests_passed << " / " << tests << " tests passed!\n";

}