Hash Functions

#include<bits/stdc++.h>
using namespace std;

const int maxN = 1000;
const int64_t p = 31;
const int64_t m = 1e9 + 9;
int64_t h[maxN],inv[maxN];

inline int64_t bin_pow (int64_t a,int64_t b) {
    a %= m;
    int64_t res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

inline void compute_hash (string & s) {
    int64_t p_pow = 1;
    inv[0] = 1;
    h[0] = s[0] - 'a' + 1;
    for (int i = 1; i < (int) s.size(); ++i) {
        p_pow = (p_pow * p) % m;
        inv[i] = bin_pow(p_pow,m - 2);
        h[i] = (h[i - 1] + (s[i] - 'a' + 1) * p_pow) % m;
    }
}

int64_t sub_hash (int l,int r) {
    int64_t res = h[r];
    if (l > 0) res -= h[l - 1];
    res *= inv[l];
    res %= m;
    return res;
}

int64_t single_hash (string & s) {
    int64_t hash_value = 0;
    int64_t 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 () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         string s,start,end;
         cin >> s >> start >> end;
         compute_hash(s);
         int64_t single_start = single_hash(start);
         int64_t single_end = single_hash(end);
         cout << single_start << ' ' << sub_hash(0,1) << '\n';
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}