fn main() { use std::io::Read; let mut buf = String::new(); std::io::stdin().read_to_string(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let s: String = iter.next().unwrap().parse::().unwrap(); let m: usize = iter.next().unwrap().parse::().unwrap(); let mut pows = [1i64;11]; for i in 0..10 { pows[i+1] = pows[i] * B % M; } let mut cnt = 0; for _ in 0..m { let c: String = iter.next().unwrap().parse::().unwrap(); cnt += search_rh(s.as_bytes(), c.as_bytes(), &pows); } println!("{}", cnt); } const B: i64 = 9973; const M: i64 = 1_000_000_007; #[doc = " O(len(base) + len(key))"] #[allow(dead_code)] pub fn search_rh(base: &[u8], key: &[u8], pows: &[i64]) -> u64 { let key_len = key.len(); let base_len = base.len(); if key_len > base_len { return 0; } let t = pows[key_len]; let mut key_h = 0; let mut base_h = 0; for i in 0..key_len { key_h = (key_h * B + key[i] as i64) % M; base_h = (base_h * B + base[i] as i64) % M; } let mut ret = 0; { let mut i = 0; while i + key_len <= base_len { if key_h == base_h { ret += 1; } if i + key_len < base_len { let p = base_h * B; let q = base[i + key_len] as i64; let r = base[i] as i64 * t; let mut z = (p + q - r) % M; if z < 0 { z += M; } base_h = z; } i += 1; } } ret }