competitive::string::rolling_hash

Trait RollingHasher

Source 
pub trait RollingHasher {
    type T;
    type Hash: Copy + Eq;

    // Required methods
    fn init_with_rng(len: usize, rng: &mut Xorshift);
    fn ensure(len: usize);
    fn hash_sequence<I>(iter: I) -> HashedSequence<Self>
       where I: IntoIterator<Item = Self::T>;
    fn hash_substr(hashed: &[Self::Hash]) -> Hashed<Self>;
    fn concat_hash(x: &Hashed<Self>, y: &Hashed<Self>) -> Hashed<Self>;
    fn empty_hash() -> Hashed<Self>;

    // Provided method
    fn init(len: usize) { ... }
}

Required Associated Types§

Source

type T

Source

type Hash: Copy + Eq

Required Methods§

Source

fn init_with_rng(len: usize, rng: &mut Xorshift)

Source

fn ensure(len: usize)

Source

fn hash_sequence<I>(iter: I) -> HashedSequence<Self>
where I: IntoIterator<Item = Self::T>,

Source

fn hash_substr(hashed: &[Self::Hash]) -> Hashed<Self>

Source

fn concat_hash(x: &Hashed<Self>, y: &Hashed<Self>) -> Hashed<Self>

Source

fn empty_hash() -> Hashed<Self>

Provided Methods§

Source

fn init(len: usize)

Examples found in repository?
crates/library_checker/src/string/zalgorithm.rs (line 19)
15pub fn zalgorithm_rolling_hash(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, s: Bytes);
19    Mersenne61x1::init(s.len());
20    let h = Mersenne61x1::hash_sequence(s.iter().map(|&c| c as _));
21    let ans = (0..s.len()).map(|i| h.range(..).longest_common_prefix(&h.range(i..)));
22    iter_print!(writer, @it ans);
23}

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§