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

//! ローリングハッシュ

use crate::{
    number_theory::modint_for_rollinghash::modint::Modint,
    utils::num_traits::{One, Zero},
};

/// ローリングハッシュ
///
/// 文字列をハッシュし，連続部分列の一致判定を $`O(1)`$ で行う．
#[derive(Debug)]
pub struct RollingHash {
    pub size: usize,
    power: Vec<Modint>,
    hash: Vec<Modint>,
    base: Modint,
}

impl RollingHash {
    /// 初期化
    pub fn build(arr: &[Modint], base: Modint) -> Self {
        let size = arr.len();
        let mut power = vec![Modint(1); size + 1];
        let mut hash = vec![Modint(0); size + 1];

        // hashを初期化
        let (mut h, mut p) = (Modint::zero(), Modint::one());
        for i in 0..size {
            h = arr[i] + (h * base);
            p *= base;
            hash[i + 1] = h;
            power[i + 1] = p;
        }

        Self {
            size,
            power,
            hash,
            base,
        }
    }

    /// 文字列から生成
    pub fn from_str(s: &str, base: Modint) -> Self {
        let arr: Vec<Modint> = s.chars().map(Self::ord).map(Modint).collect();
        Self::build(&arr, base)
    }

    /// `l..r`のハッシュを取得
    /// - 時間計算量: $`O(1)`$
    pub fn get(&self, l: usize, r: usize) -> Modint {
        self.hash[r] - self.hash[l] * self.power[r - l]
    }

    /// `0..size`のハッシュを取得
    /// - 時間計算量: $`O(1)`$
    pub fn full(&self) -> Modint {
        self.hash[self.size]
    }

    /// a,bからの最長共通接頭辞の長さを調べる
    /// - 時間計算量: $`O(\log N)`$
    pub fn getLCP(&self, a: usize, b: usize) -> usize {
        let len = self.size.saturating_sub(a.max(b));
        let (mut lo, mut hi) = (0, len + 1);
        while hi - lo > 1 {
            let mid = (lo + hi) / 2;
            if self.get(a, a + mid) == self.get(b, b + mid) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        lo
    }

    /// ハッシュ同士を連結
    /// - 時間計算量: $`O(1)`$
    pub fn concat(&self, h1: Modint, h2: Modint, h2_len: usize) -> Modint {
        h1 * self.power[h2_len] + h2
    }

    /// `A`を`0`とするascii文字(`A~Za~z`)のインデックスを返す
    #[inline]
    fn ord(c: char) -> usize {
        let a = 'A' as u32;
        let c = c as u32;
        (c - a) as usize
    }
}