Submission details
Task:Buzzwords
Sender:aalto26im_009
Submission time:2026-11-02 17:38:34 +0200
Language:Rust (2021)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.01 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.00 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.00 sdetails
#39ACCEPTED0.00 sdetails
#40ACCEPTED0.01 sdetails
#41ACCEPTED0.05 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.02 sdetails

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