Determine the number of different substrings in a string in c++ and using hashing

Viewed 259
int count_unique_substrings(string const& s) {
    int n = s.size();
    const int p = 31;
    const int m = 1e9 + 9;
    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;

    vector<long long> h(n + 1, 0);

    for (int i = 0; i < n; i++)
        h[i+1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;

    int cnt = 0;

    for (int l = 1; l <= n; l++) {
        set<long long> hs;

        for (int i = 0; i <= n - l; i++) {
            long long cur_h = (h[i + l] + m - h[i]) % m;
            cur_h = (cur_h * p_pow[n-i-1]) % m;  // unable to understand this line (how it works ?)
            hs.insert(cur_h);
        }

        cnt += hs.size();
    }
    return cnt;
}

The problem is the hash for the sub string of length l should be this:

((h[i+l] - h[i])/p_pow[i])

but the code uses:

long long cur_h = (h[i + l] + m - h[i]) % m;
cur_h = (cur_h * p_pow[n-i-1]) % m;
0 Answers
Related