Skip to main content

library_checker/string/
zalgorithm.rs

1use competitive::prelude::*;
2use competitive::string::{Mersenne61x1, RollingHasher, Zarray};
3
4#[verify::library_checker("zalgorithm")]
5pub fn zalgorithm(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(s: Chars);
8    let z = Zarray::new(&s);
9    pp!(@it (0..s.len()).map(|i| z[i]));
10}
11
12#[verify::library_checker("zalgorithm")]
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}