library_checker/string/
zalgorithm.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::string::{Mersenne61x1, RollingHasher, Zarray};
4
5#[verify::library_checker("zalgorithm")]
6pub fn zalgorithm(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, s: Chars);
10    let z = Zarray::new(&s);
11    iter_print!(writer, @it (0..s.len()).map(|i| z[i]));
12}
13
14#[verify::library_checker("zalgorithm")]
15pub fn zalgorithm_rolling_hash(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, s: Bytes);
19    Mersenne61x1::init(s.len());
20    let h = Mersenne61x1::hash_sequence(s.iter().map(|&c| c as _));
21    let ans = (0..s.len()).map(|i| h.range(..).longest_common_prefix(&h.range(i..)));
22    iter_print!(writer, @it ans);
23}