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
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106

pub mod rolling_hash {
    const MASK_30: u64 = (1 << 30) - 1;
    const MASK_31: u64 = (1 << 31) - 1;
    const MOD: u64 = (1 << 61) - 1;

    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] = modulo(mod_mul(pow[i], base));
                hash[i + 1] = modulo(mod_mul(hash[i], base) + s[i] as u64);
            }
            RollingHash {
                hash: hash,
                pow: pow,
            }
        }

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

    fn mod_mul(a: u64, b: u64) -> u64 {
        let (a_prefix, a_suffix) = (a >> 31, a & MASK_31);
        let (b_prefix, b_suffix) = (b >> 31, b & MASK_31);
        let m = a_suffix * b_prefix + a_prefix * b_suffix;
        modulo(a_prefix * b_prefix * 2 + (m >> 30) + ((m & MASK_30) << 31) + a_suffix * b_suffix)
    }

    fn modulo(v: u64) -> u64 {
        let v = (v & MOD) + (v >> 61);
        if v >= MOD {
            v - MOD
        } else {
            v
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::distributions::{IndependentSample, Range};
    use rand::{SeedableRng, StdRng};
    use test::Bencher;

    const BASE: u64 = 1_000_000_007;

    #[test]
    fn test_rolling_hash() {
        let n = 30;
        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 t = String::new() + s.as_str() + s.as_str();
            let n = t.len();
            let rolling_hash = rolling_hash::RollingHash::new(&t.as_bytes(), BASE);
            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)
                        );
                    }
                }
            }
        }
    }

    #[bench]
    fn bench_rolling_hash_construction(b: &mut Bencher) {
        let seed: &[_] = &[1, 2, 3, 4];
        let mut rng: StdRng = SeedableRng::from_seed(seed);
        let n = 100000;
        let between = Range::new(0, 26);
        let t = (0..n)
            .map(|_| between.ind_sample(&mut rng) as u8 + 'a' as u8)
            .collect::<Vec<_>>();
        b.iter(|| rolling_hash::RollingHash::new(&t, BASE));
    }
}