Rolling Hash

• Hash string $(s_0,s_1,...s_{n-1})$ to $(\sum _{i=0}^{n-1}{s}_i{x}^{n-i-1})\mathrm{mod}p$

template<typename T>
class RollingHash {
public:
    RollingHash(const std::vector<T>& s, int64_t x, int64_t p):
            p_(p), hash_(s.size() + 1), xPow_(s.size() + 1) {
        hash_[0] = 0;
        for (int i = 0; i < s.size(); ++i) {
            hash_[i + 1] = hash_[i]*x % p;
            hash_[i + 1] += s[i];
            hash_[i + 1] %= p;
        }
        
        xPow_[0] = 1;
        for (int i = 1; i < xPow_.size(); ++i) {
            xPow_[i] = (xPow_[i-1] * x) % p;
        }
    }
    
    int64_t get(int i, int j) const {
        // return s[i, j) hash
        // hash_[j] - hash_[i]*xPow[j-i]
        int64_t v = hash_[i] * xPow_[j - i] % p_;
        v = hash_[j] + (p_ - v);
        return v % p_;
    }

private:
    int64_t p_;
    vector<int64_t> hash_;
    vector<int64_t> xPow_;
};

Changelog

Last edited 13 days ago

View full history

25cf4c0-Update