Struct RollingHash

pub struct RollingHash {
    pub size: usize,
    /* private fields */
}

ローリングハッシュ

文字列をハッシュし，連続部分列の一致判定を $O(1)$ で行う．

Fields

size: usize

Implementations

impl RollingHash

pub fn build(arr: &[Modint], base: Modint) -> Self

初期化

pub fn from_str(s: &str, base: Modint) -> Self

文字列から生成

pub fn hash<'a, R: RangeBounds<usize> + Debug>( &'a self, range: R, ) -> HashVal<'a>

l..rのハッシュを取得

• 時間計算量: $O(1)$

pub fn get_LCP(&self, a: usize, b: usize) -> usize

S[a..], S[b..] の最長共通接頭辞の長さを調べる

• 時間計算量: $O(\log N)$

pub fn len(&self) -> usize

Trait Implementations

impl Debug for RollingHash

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.