Struct rolling_hash::RollingHash

pub struct RollingHash { /* private fields */ }

Rolling Hash です。O(文字列長) の前計算をしたうえで、部分文字列のハッシュ値を O(1) で計算します。

実装の参考資料

Implementations

impl RollingHash

pub fn new(xs: &[u64]) -> Self

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn at(&self, i: usize) -> u64

pub fn hash(&self, range: Range<usize>) -> u64

部分文字列のハッシュ値を返します。

pub fn is_substring(&self, other: &Self) -> bool

self が other の部分文字列かどうかを返します。

O(other.len())

Examples

use rolling_hash::RollingHash;
let rh1 = RollingHash::from_iter("abcd".bytes());
let rh2 = RollingHash::from_iter("xxabcdyy".bytes());
assert!(rh1.is_substring(&rh2));

Trait Implementations

impl Clone for RollingHash

fn clone(&self) -> RollingHash

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for RollingHash

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

Formats the value using the given formatter.

impl<T> FromIterator<T> for RollingHashwhere T: Into<u64>,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.