Fast Substring Hashing Implementation

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

using namespace std;

long long m = 1e9 + 9;
long long p = 31;

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

// returns a vector of size n+1 where inverse_ptoa[i] = inverse_mod(p^a)
vector<long long> comp_inverse_ptoa(int n)
{
    vector<long long> inverse_ptoa;
    for (int a = 0; a <= n; a++)
        inverse_ptoa.push_back(fast_pow(fast_pow(p, a), m - 2));
    return inverse_ptoa;
}

// returns a vector where pref_hash[i] = hash(s[0...i-1])
vector<long long> comp_pref_hash(string& s)
{
    vector<long long> pref_hash;
    int n = s.size();
    vector<long long> p_pow(n);
    p_pow[0] = 1;
    for (int i = 1; i < n; i++)
        p_pow[i] = (p_pow[i - 1] * p) % m;

    pref_hash.push_back(0);
    for (int i = 0; i < n; i++)
        pref_hash.push_back(((pref_hash[i] + ((s[i] - 'a' + 1) * p_pow[i]) % m)) % m);
    return pref_hash;
}

// returns hash(s[a...b]) in O(1)
long long substr_hash(vector<long long>& inverse_ptoa, vector<long long>& pref_hash, int a, int b)
{
    return inverse_ptoa[a] * ((m + (pref_hash[b] - pref_hash[a])) % m) % m;
}

// 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 - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

int main()
{
    string s = "supercallifragilisticexpialidocious";
    int n = s.size();
    vector<long long> inverse_ptoa1 = comp_inverse_ptoa(n);
    vector<long long> pref_hash1 = comp_pref_hash(s);

    int tests_passed = 0;
    int tests = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            string sub = s.substr(i, j - i);
            int fast_hash = substr_hash(inverse_ptoa1,pref_hash1, 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";

}