# -*- mode: snippet -*-
# name: rolling hash
# contributor: Nakamura Kenko
# key: rollinghash
# --
pub struct RollingHash {
    hash: Vec<u64>,
    pow: Vec<u64>,
}

impl RollingHash {
    pub fn new(s: &[u8], base: u64) -> RollingHash {
        let n = s.len();
        let mut hash: Vec<u64> = vec![0; n + 1];
        let mut pow: Vec<u64> = vec![0; n + 1];
        pow[0] = 1;
        for i in 0..n {
            pow[i + 1] = pow[i].wrapping_mul(base);
            hash[i + 1] = hash[i].wrapping_mul(base).wrapping_add(s[i] as u64);
        }
        RollingHash {
            hash: hash,
            pow: pow,
        }
    }

    /// Get hash of [l, r)
    pub fn get_hash(&self, l: usize, r: usize) -> u64 {
        self.hash[r].wrapping_sub(self.hash[l].wrapping_mul(self.pow[r - l]))
    }
}

