Rolling Hash + Segment Tree
(string/rolling-hash-segment-tree/src/lib.rs)

• View this file on GitHub
• Last update: 2025-06-07 00:31:50+09:00

Description

Depends on

• Segment Tree (data-structure/segment-tree/src/lib.rs)
• data-structure/segment-tree/src/wrapper.rs

Verified with

• verification/aizu-online-judge/alds1_14_b/src/main.rs

Code

use segment_tree::SegmentTree;

#[derive(Debug, Clone)]
pub struct RollingHash<T> {
    base: T,
    power: Vec<T>,
}

impl<T: Copy + From<u64>> RollingHash<T>
where
    T: std::ops::Add<T, Output = T>,
    T: std::ops::AddAssign,
    T: std::ops::Sub<T, Output = T>,
    T: std::ops::SubAssign,
    T: std::ops::Mul<T, Output = T>,
    T: std::ops::MulAssign,
    T: std::ops::Div<T, Output = T>,
    T: std::ops::DivAssign,
{
    pub fn new(base: T) -> Self {
        Self {
            base,
            power: vec![T::from(1u64)],
        }
    }

    pub fn build_segment_tree(&mut self, s: &Vec<char>) -> SegmentTree<(T, T)> {
        let size = s.len();
        let mut st = SegmentTree::<(T, T)>::new(size, |a, b| (a.0 + (a.1 * b.0), a.1 * b.1), (T::from(0u64), T::from(1u64)));
        for i in 0..size {
            st.set(i, (T::from(s[i] as u64), self.base));
        }
        st
    }

    pub fn build(&mut self, s: &Vec<char>) -> Vec<T> {
        let size = s.len();
        let mut hash = vec![T::from(0u64); size + 1];
        for i in 0..size {
            hash[i + 1] = hash[i] * self.base + T::from(s[i] as u64);
        }
        hash
    }

    fn build_power(&mut self, r: usize) {
        while self.power.len() <= r {
            let val = *self.power.last().unwrap();
            self.power.push(val * self.base);
        }
    }

    // [l, r)
    pub fn rolling_hash(&mut self, hash: &Vec<T>, l: usize, r: usize) -> T {
        assert!(l <= r && r <= hash.len());
        self.build_power(r - l);
        hash[r] - hash[l] * self.power[r - l]
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page