Struct cp_library_rs::string::rolling_hash::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 get(&self, l: usize, r: usize) -> Modint

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

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

pub fn full(&self) -> Modint

0..sizeのハッシュを取得

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

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

a,bからの最長共通接頭辞の長さを調べる

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

pub fn concat(&self, h1: Modint, h2: Modint, h2_len: usize) -> Modint

ハッシュ同士を連結

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

Trait Implementations

impl Debug for RollingHash

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

Formats the value using the given formatter.