| Task: | Buzzwords |
| Sender: | aalto26im_009 |
| Submission time: | 2026-11-02 17:38:34 +0200 |
| Language: | Rust (2021) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | ACCEPTED | 0.00 s | details |
| #3 | ACCEPTED | 0.00 s | details |
| #4 | ACCEPTED | 0.00 s | details |
| #5 | ACCEPTED | 0.00 s | details |
| #6 | ACCEPTED | 0.00 s | details |
| #7 | ACCEPTED | 0.00 s | details |
| #8 | ACCEPTED | 0.00 s | details |
| #9 | ACCEPTED | 0.00 s | details |
| #10 | ACCEPTED | 0.00 s | details |
| #11 | ACCEPTED | 0.00 s | details |
| #12 | ACCEPTED | 0.00 s | details |
| #13 | ACCEPTED | 0.00 s | details |
| #14 | ACCEPTED | 0.00 s | details |
| #15 | ACCEPTED | 0.00 s | details |
| #16 | ACCEPTED | 0.00 s | details |
| #17 | ACCEPTED | 0.00 s | details |
| #18 | ACCEPTED | 0.00 s | details |
| #19 | ACCEPTED | 0.00 s | details |
| #20 | ACCEPTED | 0.00 s | details |
| #21 | ACCEPTED | 0.00 s | details |
| #22 | ACCEPTED | 0.00 s | details |
| #23 | ACCEPTED | 0.00 s | details |
| #24 | ACCEPTED | 0.00 s | details |
| #25 | ACCEPTED | 0.00 s | details |
| #26 | ACCEPTED | 0.00 s | details |
| #27 | ACCEPTED | 0.00 s | details |
| #28 | ACCEPTED | 0.00 s | details |
| #29 | ACCEPTED | 0.00 s | details |
| #30 | ACCEPTED | 0.00 s | details |
| #31 | ACCEPTED | 0.00 s | details |
| #32 | ACCEPTED | 0.01 s | details |
| #33 | ACCEPTED | 0.00 s | details |
| #34 | ACCEPTED | 0.00 s | details |
| #35 | ACCEPTED | 0.00 s | details |
| #36 | ACCEPTED | 0.00 s | details |
| #37 | ACCEPTED | 0.00 s | details |
| #38 | ACCEPTED | 0.00 s | details |
| #39 | ACCEPTED | 0.00 s | details |
| #40 | ACCEPTED | 0.01 s | details |
| #41 | ACCEPTED | 0.05 s | details |
| #42 | ACCEPTED | 0.01 s | details |
| #43 | ACCEPTED | 0.01 s | details |
| #44 | ACCEPTED | 0.02 s | details |
Code
#![allow(unused)]
use std::hash::Hash;
use std::io;
use std::{
collections::*,
io::{prelude::*, *},
};
use std::sync::OnceLock;
use std::time::{SystemTime, UNIX_EPOCH};
const M1: u64 = 1_000_000_007;
const M2: u64 = 1_000_000_009;
static BASES: OnceLock<(u64, u64)> = OnceLock::new();
fn bases() -> (u64, u64) {
*BASES.get_or_init(|| {
fn splitmix(x: u64) -> u64 {
let mut z = x.wrapping_add(0x9E3779B97F4A7C15);
z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
z ^ (z >> 31)
}
let seed = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos() as u64;
let b1 = 256 + splitmix(seed) % (M1 - 256);
let b2 = 256 + splitmix(seed ^ 0xDEADBEEF) % (M2 - 256);
(b1, b2)
})
}
struct StrHash {
h1: Vec<u64>,
h2: Vec<u64>,
p1: Vec<u64>,
p2: Vec<u64>,
}
impl StrHash {
fn new(s: &[u8]) -> Self {
let (b1, b2) = bases();
let n = s.len();
let (mut h1, mut h2) = (vec![0; n + 1], vec![0; n + 1]);
let (mut p1, mut p2) = (vec![1; n + 1], vec![1; n + 1]);
for i in 0..n {
let c = s[i] as u64;
h1[i + 1] = (h1[i] * b1 + c) % M1;
h2[i + 1] = (h2[i] * b2 + c) % M2;
p1[i + 1] = p1[i] * b1 % M1;
p2[i + 1] = p2[i] * b2 % M2;
}
StrHash { h1, h2, p1, p2 }
}
fn get(&self, l: usize, r: usize) -> u64 {
let x1 = (self.h1[r] + M1 - self.h1[l] * self.p1[r - l] % M1) % M1;
let x2 = (self.h2[r] + M2 - self.h2[l] * self.p2[r - l] % M2) % M2;
(x1 << 32) | x2
}
}
fn take_string() -> Vec<u8> {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let vec: Vec<u8> = input.trim().as_bytes().to_vec();
vec
}
fn take_int() -> usize {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
return input.trim().parse::<usize>().unwrap();
}
fn main() {
let mut s = take_string();
let mut q = take_int();
let mut words: Vec<Vec<u8>> = Vec::with_capacity(q);
let mut max = 1;
for i in 0..q {
let w = take_string();
max = max.max(w.len());
words.push(w);
}
let mut hm: HashMap<u64, usize> = HashMap::new();
let hs = StrHash::new(&s);
for i in 0..s.len() {
for j in 1..max+1 {
if i+j > s.len() {
continue;
}
let mut k: u64 = hs.get(i,i+j);
let mut value = hm.entry(k).or_insert(0usize);
*value += 1;
}
}
let mut sum = 0;
for i in &words {
let k = StrHash::new(i);
let key = k.get(0,i.len());
sum += hm.get(&key).unwrap_or(&0usize);
}
println!("{}", sum)
}
Test details
Test 1
Verdict: ACCEPTED
| input |
|---|
| g fhe 395 a aa aafh ... |
| correct output |
|---|
| 10 |
| user output |
|---|
| 10 |
Test 2
Verdict: ACCEPTED
| input |
|---|
| s adh 372 a ad ae ... |
| correct output |
|---|
| 6 |
| user output |
|---|
| 6 |
Test 3
Verdict: ACCEPTED
| input |
|---|
| adcdb 20 a aa ab ... |
| correct output |
|---|
| 9 |
| user output |
|---|
| 9 |
Test 4
Verdict: ACCEPTED
| input |
|---|
| aaaaa 5 a aa aaa ... |
| correct output |
|---|
| 15 |
| user output |
|---|
| 15 |
Test 5
Verdict: ACCEPTED
| input |
|---|
| o zws 759 a ab abw ... |
| correct output |
|---|
| 8 |
| user output |
|---|
| 8 |
Test 6
Verdict: ACCEPTED
| input |
|---|
| aaaaa 5 a aa aaa ... |
| correct output |
|---|
| 15 |
| user output |
|---|
| 15 |
Test 7
Verdict: ACCEPTED
| input |
|---|
| ifv b 649 a aaw ac ... |
| correct output |
|---|
| 10 |
| user output |
|---|
| 10 |
Test 8
Verdict: ACCEPTED
| input |
|---|
| dbbdc 129 a aa aaab ... |
| correct output |
|---|
| 15 |
| user output |
|---|
| 15 |
Test 9
Verdict: ACCEPTED
| input |
|---|
| aaaaa 5 a aa aaa ... |
| correct output |
|---|
| 15 |
| user output |
|---|
| 15 |
Test 10
Verdict: ACCEPTED
| input |
|---|
| eeeab 9 a b c ... |
| correct output |
|---|
| 5 |
| user output |
|---|
| 5 |
Test 11
Verdict: ACCEPTED
| input |
|---|
| ghfhe d fd 430 a aa aafa ... |
| correct output |
|---|
| 22 |
| user output |
|---|
| 22 |
Test 12
Verdict: ACCEPTED
| input |
|---|
| syadhzdgck 275 a ad adh ... |
| correct output |
|---|
| 53 |
| user output |
|---|
| 53 |
Test 13
Verdict: ACCEPTED
| input |
|---|
| adcdbbbbba 256 a aa aaa ... |
| correct output |
|---|
| 49 |
| user output |
|---|
| 49 |
Test 14
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaa 10 a aa aaa ... |
| correct output |
|---|
| 55 |
| user output |
|---|
| 55 |
Test 15
Verdict: ACCEPTED
| input |
|---|
| o zwspspfd 468 a adks afhsrhvwxn ... |
| correct output |
|---|
| 45 |
| user output |
|---|
| 45 |
Test 16
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaa 10 a aa aaa ... |
| correct output |
|---|
| 55 |
| user output |
|---|
| 55 |
Test 17
Verdict: ACCEPTED
| input |
|---|
| i vbbjczpc 703 a aa abou ... |
| correct output |
|---|
| 29 |
| user output |
|---|
| 29 |
Test 18
Verdict: ACCEPTED
| input |
|---|
| d bdcbdbcb 128 a aa aab ... |
| correct output |
|---|
| 42 |
| user output |
|---|
| 42 |
Test 19
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaa 10 a aa aaa ... |
| correct output |
|---|
| 55 |
| user output |
|---|
| 55 |
Test 20
Verdict: ACCEPTED
| input |
|---|
| eeeabcbabh 171 a aac aahg ... |
| correct output |
|---|
| 34 |
| user output |
|---|
| 34 |
Test 21
Verdict: ACCEPTED
| input |
|---|
| ghfhehdf ddciaicdehheefdihadaf... |
| correct output |
|---|
| 246 |
| user output |
|---|
| 246 |
Test 22
Verdict: ACCEPTED
| input |
|---|
| s adhzdgckekirkyowkirnflwfanrx... |
| correct output |
|---|
| 52 |
| user output |
|---|
| 52 |
Test 23
Verdict: ACCEPTED
| input |
|---|
| adcdbbbbbaaccabbbccd cabccacdb... |
| correct output |
|---|
| 178 |
| user output |
|---|
| 178 |
Test 24
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| 2518 |
| user output |
|---|
| 2518 |
Test 25
Verdict: ACCEPTED
| input |
|---|
| oezws spfdzfasgxlquafowjzpe pv... |
| correct output |
|---|
| 284 |
| user output |
|---|
| 284 |
Test 26
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| 1387 |
| user output |
|---|
| 1387 |
Test 27
Verdict: ACCEPTED
| input |
|---|
| ifvbbjczpcnpknimqvlttkngpe szx... |
| correct output |
|---|
| 258 |
| user output |
|---|
| 258 |
Test 28
Verdict: ACCEPTED
| input |
|---|
| dbbdcbdb bcaabb bccddbbbacbcdc... |
| correct output |
|---|
| 36 |
| user output |
|---|
| 36 |
Test 29
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| 3076 |
| user output |
|---|
| 3076 |
Test 30
Verdict: ACCEPTED
| input |
|---|
| e eabcbabhdbcbaddebchdiga ggfb... |
| correct output |
|---|
| 23 |
| user output |
|---|
| 23 |
Test 31
Verdict: ACCEPTED
| input |
|---|
| ghfhehdff dci icdehheefdih daf... |
| correct output |
|---|
| 248 |
| user output |
|---|
| 248 |
Test 32
Verdict: ACCEPTED
| input |
|---|
| s a hzdgckekirkyo kirnflw anrx... |
| correct output |
|---|
| 27 |
| user output |
|---|
| 27 |
Test 33
Verdict: ACCEPTED
| input |
|---|
| adcdbbb baac abbbcc c abccacd ... |
| correct output |
|---|
| 433 |
| user output |
|---|
| 433 |
Test 34
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| 3427 |
| user output |
|---|
| 3427 |
Test 35
Verdict: ACCEPTED
| input |
|---|
| oezwsp pf z asgxlquafowjzpekpv... |
| correct output |
|---|
| 359 |
| user output |
|---|
| 359 |
Test 36
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| 2126 |
| user output |
|---|
| 2126 |
Test 37
Verdict: ACCEPTED
| input |
|---|
| ifvbbjczpcnpk imqvlttkngpeqszx... |
| correct output |
|---|
| 395 |
| user output |
|---|
| 395 |
Test 38
Verdict: ACCEPTED
| input |
|---|
| dbbdcbd cbcaabbabccddbb acbcdc... |
| correct output |
|---|
| 242 |
| user output |
|---|
| 242 |
Test 39
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| 4287 |
| user output |
|---|
| 4287 |
Test 40
Verdict: ACCEPTED
| input |
|---|
| eeeabcbabhd cb ddebchdigaiggfb... |
| correct output |
|---|
| 15 |
| user output |
|---|
| 15 |
Test 41
Verdict: ACCEPTED
| input |
|---|
| ghfhehdffdd i icdehheefd hadaf... |
| correct output |
|---|
| 431 |
| user output |
|---|
| 431 |
Test 42
Verdict: ACCEPTED
| input |
|---|
| syadhzdgckekirkyow irnflwfanrx... |
| correct output |
|---|
| 8039 |
| user output |
|---|
| 8039 |
Test 43
Verdict: ACCEPTED
| input |
|---|
| adcdbbbbbaaccabb ccdccabcc cdb... |
| correct output |
|---|
| 9409 |
| user output |
|---|
| 9409 |
Test 44
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| 168696 |
| user output |
|---|
| 168696 |
