String Hashing

Concept

Define the hash of a string $S$ of length $n$ as follow: $$ \text{hash}(S) = \sum_{i=1}^{n} S[i-1] \times p^{n - i} \text{ mod } m $$

To compute $H(S, m) = \text{hash}(S[0...m])$ for $m = 0$ to $n-1$, we can take use of the previous computed value: $$ H(S, m) = H(S, m-1) \times p + S[m] \text{ mod } m $$

With $H(S, m)$, we can compute $H(S, \ell, r) = \text{hash}(S[\ell...r])$ in $\Theta(1)$: $$ H(S, \ell, r) = H(S, r) - H(S, \ell-1) \times p^{r-\ell+1} \text{ mod } m $$

Implementation

struct StrHasher {
    int p, m;
    vector<int> p_pow;

    StrHasher(int max_len, int _p=256, int _m=1e9+7): p(_p), m(_m) {
        p_pow.resize(max_len+1);
        p_pow[0] = 1;
        for (int i = 1; i <= max_len; i++)
            p_pow[i] = (1ll * p_pow[i-1] * p) % m;
    }

    vector<int> hash(const string& S) {
        vector<int> H(S.length(), 0);
        H[0] = S[0];
        for (int i = 1; i < S.length(); i++)
            H[i] = (1ll * H[i-1] * p + S[i]) % m;
        return H;
    }

    int get_hash(vector<int>&H, int l, int r) {
        if (l == 0) return H[r];
        else return (H[r] - 1ll * H[l-1] * p_pow[r-l+1] % m + m) % m;
    }
};