String Hashing (Number of Different Substrings)

int single_hash (const string & s) {
    const int p = 31;
    const int m = 1e9 + 9;
    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 compute_hash (const string & s) {
    int n = (int) s.size();
    const int p = 31;
    const int m = 1e9 + 9;
    vector<int64_t> p_pow(n);
    p_pow[0] = 1;
    for (int i= 1; i < n; ++i) p_pow[i] = (p_pow[i - 1] * p) % m;
    vector<int64_t> h(n + 1,0);
    for (int i = 0; i < n; ++i) {
        h[i + 1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;
    }
    //number of different substring(for small length)
    int cnt = 0;
    for (int l = 1; l <= n; ++l) {
        set<int64_t> hs;
        for (int i = 0; i <= n - l; ++i) {
            int64_t cur_h = (h[i + l] + m - h[i]) % m;
            cur_h = (cur_h * p_pow[n - i - 1]) % m;
            hs.insert(cur_h);
        }
        cnt += (int) hs.size();
    }
    return cnt;
}