use proconio::{input, marker::Bytes}; fn main() { input! { s: Bytes, m: usize, c: [Bytes; m], } let rh = RollingHash::build(s.clone()); let mut crh = vec![]; for i in 0..m { let tmp = RollingHash::build(c[i].clone()); crh.push(tmp); } let mut ans = 0; for i in 0..m { let len = c[i].len(); for j in 0..s.len() - len { if crh[i].get(0, c[i].len()) == rh.get(j, j + len) { ans += 1; } } } println!("{ans}"); } const MOD: usize = 999_999_937; const BASE: usize = 3491; #[allow(unused)] struct RollingHash { s: Vec, prefix: Vec, power: Vec, } #[allow(unused)] impl RollingHash { pub fn build(s: Vec) -> Self { let n = s.len(); let mut prefix = vec![0; n + 1]; let mut power = vec![1; n + 1]; for i in 0..n { let c = (s[i] - b'a' + 1) as usize; prefix[i + 1] = (prefix[i] * BASE + c) % MOD; power[i + 1] = (power[i] * BASE) % MOD; } RollingHash { s: s, prefix: prefix, power: power, } } pub fn get(&self, l: usize, r: usize) -> usize { (self.prefix[r] - self.power[r - 1] * self.prefix[l]) % MOD } }