Skip to main content

RollingHasher

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 16)
13pub fn zalgorithm_rolling_hash(reader: impl Read, writer: impl Write) {
14    prepare_io!(reader, writer);
15    sc!(s: Bytes);
16    Mersenne61x1::init(s.len());
17    let h = Mersenne61x1::hash_sequence(s.iter().map(|&c| c as _));
18    let ans = (0..s.len()).map(|i| h.range(..).longest_common_prefix(&h.range(i..)));
19    pp!(@it ans);
20}

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§