haar_lib/algo/
rolling_hash.rs

1//! Rolling Hash
2use std::ops::Range;
3
4/// 文字列のハッシュ値を計算する構造体。
5pub struct RollingHash {
6    m: u64,
7    b: u64,
8    pow: Vec<u64>,
9}
10
11impl RollingHash {
12    /// 最大長`size`、基数`b`と剰余の除数`m`を設定した[`RollingHash`]を用意する。
13    pub fn new(size: usize, m: u64, b: u64) -> Self {
14        let mut pow = vec![1; size + 1];
15
16        for i in 1..=size {
17            pow[i] = pow[i - 1] * b % m;
18        }
19
20        Self { m, b, pow }
21    }
22
23    /// 文字列`s`のハッシュを計算する。
24    pub fn hash(&self, s: &str) -> u64 {
25        s.as_bytes()
26            .iter()
27            .fold(0, |acc, c| (acc * self.b + *c as u64) % self.m)
28    }
29
30    /// 文字列`s`からハッシュ計算テーブルを作る。
31    pub fn hash_table(&self, s: &str) -> Table {
32        let mut ret = vec![1; s.len() + 1];
33
34        for (i, c) in s.as_bytes().iter().enumerate() {
35            ret[i + 1] = (ret[i] * self.b + *c as u64) % self.m;
36        }
37
38        Table {
39            table: ret,
40            rh: self,
41        }
42    }
43}
44
45/// [`RollingHash::hash_table`]で返される、部分列のハッシュ値計算用の構造体。
46pub struct Table<'a> {
47    table: Vec<u64>,
48    rh: &'a RollingHash,
49}
50
51impl Table<'_> {
52    /// 範囲`l..r`でのハッシュを計算する。
53    pub fn hash(&self, Range { start: l, end: r }: Range<usize>) -> u64 {
54        let m = self.rh.m;
55        (self.table[r] - self.table[l] * self.rh.pow[r - l] % m + m * m) % m
56    }
57}
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test() {
65        let rh = RollingHash::new(100, 10_u64.pow(9) + 7, 123);
66
67        let s = "abracadabra";
68
69        let table = rh.hash_table(s);
70
71        let p = "ab";
72        let h = rh.hash(p);
73
74        for from in 0..s.len() - p.len() {
75            let to = from + p.len();
76
77            if table.hash(from..to) == h {
78                dbg!(from, to, &s[from..to]);
79            }
80        }
81    }
82}
haar_lib/algo/rolling_hash.rs

haar_lib/algo/
rolling_hash.rs
