verify/yosupo/zalgorithm_rolling_hash/src/main.rs

View this file on GitHub
Last update: 2024-10-31 15:27:16+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

crates/string/rolling_hash/src/lib.rs

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/zalgorithm

#![allow(non_snake_case)]
use proconio::{fastout, input, marker::Chars};
use rolling_hash::RollingHash;

#[fastout]
fn main() {
    input! {
        S: Chars,
    }
    let rh = RollingHash::new(&S, None);
    for i in 0..S.len() {
        // [i, i) ~ [i, S.len() + 1) で二分探索
        let mut left = i;
        let mut right = S.len() + 1;
        while right - left > 1 {
            let mid = (left + right) / 2;
            if rh.get_hash(i..mid) == rh.get_prefix_hash(mid - i) {
                left = mid;
            } else {
                right = mid;
            }
        }
        print!("{} ", left - i);
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/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.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError