use proconio::{input, marker::Chars}; // 430 fn main() { input! { S: Chars, M: usize, C: [String; M] }; let mut cnt = 0; for i in 0..M { if S.len() < C[i].len() { continue; } for j in 0..=(S.len() - C[i].len()) { if contain(&C[i], &S[j..(j + C[i].len())].iter().collect::()) { cnt += 1; } } } println!("{}", cnt); } fn contain(a: &String, b: &String) -> bool { const B: u64 = 1000000007; let a = a.as_bytes(); let b = b.as_bytes(); let al = a.len(); let bl = b.len(); if al > bl { return false; } let mut ah = 0u64; let mut bh = 0u64; for i in 0..al { ah = ah.wrapping_mul(B).wrapping_add(a[i] as u64); bh = bh.wrapping_mul(B).wrapping_add(b[i] as u64); } let t = B.wrapping_pow(al as u32); for i in 0..=(bl - al) { if ah == bh { return true; } if i + al < bl { bh = bh.wrapping_mul(B).wrapping_add(b[i + al] as u64).wrapping_sub((b[i] as u64).wrapping_mul(t)); } } false }