1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

pub struct RollingHash {
    base: u64,
    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 {
            base: base,
            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]))
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::distributions::{IndependentSample, Range};
    const MOD: u64 = 1_000_000_007;

    #[test]
    fn test_rolling_hash() {
        let n = 100;
        let between = Range::new(0, 26);
        let mut rng = rand::thread_rng();

        for _ in 0..100 {
            let mut s = String::new();
            for _ in 0..n {
                let c = (between.ind_sample(&mut rng) as u8 + 'a' as u8) as char;
                s.push(c);
            }

            let mut t = String::new() + s.as_str() + s.as_str();

            let rolling_hash = RollingHash::new(&t.as_bytes(), MOD);
            for i in 0..n {
                for j in i..n {
                    for k in (j + 1)..n {
                        let same = t[i..k] == t[j..k];
                        let same_hash = rolling_hash.get_hash(i, k) == rolling_hash.get_hash(j, k);
                        assert_eq!(
                            same,
                            same_hash,
                            "{:?} {:?} {} {}",
                            &t[i..k],
                            &t[j..k],
                            rolling_hash.get_hash(i, k),
                            rolling_hash.get_hash(j, k)
                        );
                    }
                }
            }
        }
    }
}