#[allow(unused_macros)] macro_rules ! for_ { ( $ init : stmt ; $ cond : expr ; $ incr : expr , $ body : block ) => ( { $ init ; while $ cond { $ body $ incr ; } } ) ; } 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 cnt = 0; for _ in 0..m { let c: String = iter.next().unwrap().parse::().unwrap(); cnt += search_rh(s.as_bytes(), c.as_bytes()).len(); } println!("{}", cnt); } #[doc = " O(len(base) + len(key))"] #[allow(dead_code)] pub fn search_rh(base: &[u8], key: &[u8]) -> Vec { const B: i64 = 9973; const M: i64 = 1_000_000_007; let key_len = key.len(); let base_len = base.len(); if key_len > base_len { return vec![]; } let mut t = 1i64; for _ in 0..key_len { t *= B; t %= M; } let mut key_h = 0; let mut base_h = 0; for i in 0..key_len { key_h = ((key_h * B) % M + (key[i] as i64) % M) % M; base_h = ((base_h * B) % M + (base[i] as i64) % M) % M; } let mut ret = vec![]; for_!(let mut i = 0; i + key_len <= base_len; i += 1, { if key_h == base_h {ret.push(i);} 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; } }); ret }