nekolib/utils/
op_roll_hash.rs

1//! ローリングハッシュに関する wrapper クラス。
2
3use super::super::traits::binop;
4
5use std::fmt::Debug;
6
7use binop::{Associative, Identity, Magma};
8
9/// 文字列連結をローリングハッシュで行う演算を持つ。
10///
11/// # Examples
12/// ```
13/// use nekolib::traits::Magma;
14/// use nekolib::utils::OpRollHash;
15///
16/// let op_rh = OpRollHash::<998244353>::default();
17/// let value_of = |s| op_rh.value_of(s);
18/// let op = |x, y| op_rh.op(x, y);
19///
20/// let abr = value_of("abr");
21/// let a = value_of("a");
22/// let abra = value_of("abra");
23/// assert_eq!(op(abr, a), abra);
24///
25/// let s = "abracadabra";
26/// assert_eq!(value_of(&s[0..4]), abra);
27/// assert_eq!(value_of(&s[7..11]), abra);
28/// assert_ne!(value_of(&s[1..5]), abra);
29/// assert_eq!(value_of(s), op(op(abra, value_of("cad")), abra));
30/// ```
31#[derive(Clone, Copy, Debug, Eq, PartialEq)]
32pub enum OpRollHash<const B: u64> {
33    OpRollHashV,
34}
35pub use OpRollHash::OpRollHashV;
36
37impl<const B: u64> Default for OpRollHash<B> {
38    fn default() -> Self { OpRollHashV }
39}
40
41impl<const B: u64> Magma for OpRollHash<B> {
42    type Set = (u64, u64);
43    fn op(&self, (hx, lx): Self::Set, (hy, ly): Self::Set) -> Self::Set {
44        ((hx * ly + hy) % B, (lx * ly) % B)
45    }
46}
47
48impl<const B: u64> Identity for OpRollHash<B> {
49    fn id(&self) -> Self::Set { (0, 1) }
50}
51
52impl<const B: u64> Associative for OpRollHash<B> {}
53
54impl<const B: u64> OpRollHash<B> {
55    #[must_use]
56    pub fn value_of(&self, s: &str) -> <Self as Magma>::Set {
57        s.chars().fold((0, 0), |acc, x| self.op(acc, (x as u64, B)))
58    }
59}
nekolib/utils/op_roll_hash.rs

nekolib/utils/
op_roll_hash.rs
