Struct comlib_string::RollingHash

pub struct RollingHash<M = Mod1e9p7> where
    M: InvertibleModulus + Copy,  { /* fields omitted */ }

Rolling hash for strings

Current implementation

The rolling hash is based on the following idea: Let s = c0c1c2…cn-1 be a string and let x be an element of a modular group. Now we can construct a hash h = c0 + c1x + c2x2 + … + cn-1xn-1 for the whole string. Because h is evaluated in a modular group, it is not unique, but it is unlikely to find two strings which produce the same hash unless they are produced by an adversary¹. Now the interesting part is that we can compute the hash for any substring sl…r = clcl+1…cr-1cr as hl…r = (clxl + cl+1xl+1 + … + crxr) / xl. The sum can be computed efficiently by storing the terms in a Binary indexed tree which allow querying the sum over a range in O(log n) time. The Binary indexed tree also allows updating the terms of the sum in O(log n) time meaning that we can modify the string one character at a time.

¹: The change of a collision attack is tried to be mitigated by randomly choosing the value of x for each run.

Implementations

impl<M> RollingHash<M> where
    M: InvertibleModulus + Copy + Default,
    M::Base: From<u64>, 

pub fn new<S: AsRef<str>>(input: S) -> Self

Constructs new RollingHash.

The x is chosen randomly

pub fn with_x<S: AsRef<str>>(input: S, x: ModInt<M>) -> Self

Constructs new RollingHash which uses the given x.

pub fn get_hash<R: RangeBounds<usize>>(&self, range: R) -> ModInt<M>

Gets the hash of the substring over the given range.

Note that the range is given in characters, not in bytes like with str.

pub fn set_char(&mut self, index: usize, new_char: char)

Replaces the character at the given index with new one.

pub fn x(&self) -> ModInt<M>

Returns the x used for hashing.

Trait Implementations

impl<M: Clone> Clone for RollingHash<M> where
    M: InvertibleModulus + Copy, 

fn clone(&self) -> RollingHash<M>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.