提出 #19087694

---

ソースコード 拡げる

use std::collections::BTreeMap;

const MASK_30: u64 = (1 << 30) - 1;
const MASK_31: u64 = (1 << 31) - 1;
const MOD: u64 = (1 << 61) - 1;
const BASE: u64 = 1e9 as u64 + 7;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let k: usize = sc.read();
    let s: Vec<usize> = sc
        .read::<String>()
        .chars()
        .map(|c| c as usize - 'a' as usize)
        .collect();
    let mut base = vec![1; 26];
    for i in 1..26 {
        base[i] = mod_mul(base[i - 1], BASE);
    }

    let mut sum = 0;
    for i in 0..k {
        sum += base[s[i]];
        sum %= MOD;
    }

    let mut sum_hash = vec![sum];
    for i in k..n {
        sum += base[s[i]];
        sum += MOD - base[s[i - k]];
        sum %= MOD;
        sum_hash.push(sum);
    }

    let mut sum_count = BTreeMap::new();
    for i in 0..(n - k + 1) {
        if i >= k {
            *sum_count.entry(sum_hash[i - k]).or_insert(0) += 1;
        }
        let sum_cur = sum_count.get(&sum_hash[i]).cloned().unwrap_or(0);
        if sum_cur > 0 {
            println!("YES");
            return;
        }
    }
    println!("NO");
}

fn mod_mul(a: u64, b: u64) -> u64 {
    let (a_prefix, a_suffix) = (a >> 31, a & MASK_31);
    let (b_prefix, b_suffix) = (b >> 31, b & MASK_31);
    let m = a_suffix * b_prefix + a_prefix * b_suffix;
    modulo(a_prefix * b_prefix * 2 + (m >> 30) + ((m & MASK_30) << 31) + a_suffix * b_suffix)
}

fn modulo(v: u64) -> u64 {
    let v = (v & MOD) + (v >> 61);
    if v >= MOD {
        v - MOD
    } else {
        v
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

提出情報

ジャッジ結果