Hashing

 avatar
unknown
c_cpp
3 years ago
1.4 kB
2
Indexable
class Hashing {
private:
    const int mod = (int) 1e9 + 7;
    const int p = 53; // should be prime
    string s;
    int n;
    vector<long long> h1, h2;
    vector<long long> p1, p2;
public:
    void init(string st) {
        s = st;
        n = (int) s.length();

        p1.assign(n + 1, 1); 
        p2.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            p1[i] = p1[i - 1] * p;
            p2[i] = p2[i - 1] * p % mod; 
        }

        char minChar = s[0];
        for (int i = 0; i < n; i++) minChar = min(minChar, s[i]);

        h1.assign(n, 0); 
        h2.assign(n, 0);
        h1[0] = s[0] - minChar + 1;
        h2[0] = (s[0] - minChar + 1) % mod;
        for (int i = 1; i < n; i++) {
            h1[i] = h1[i - 1] + p1[i] * (s[i] - minChar + 1);
            h2[i] = (h2[i - 1] + p2[i] * (s[i] - minChar + 1)) % mod; 
        }
    }
    long long getHash1(int l, int r) {
        long long h = h1[r];
        if (l > 0)
            h -= h1[l - 1];
        h *= p1[n - 1 - r];
        return h;
    }
    long long getHash2(int l, int r) {
        long long h = h2[r];
        if (l > 0)
            h = (h - h2[l - 1] + mod) % mod;
        h = h * p2[n - 1 - r] % mod;
        return h;
    }
    pair<long long, long long> getHash(int l, int r) {
        return {getHash1(l, r), getHash2(l, r)};
    }
};