#[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: u64 = 9973; const M: u64 = 1_000_000_007; let key_len = key.len(); let base_len = base.len(); if key_len > base_len {return vec![];} let mut t = 1u64; 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 u64) % M) % M; base_h = ((base_h * B) % M + (base[i] as u64) % 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 mut left = base_h * B % M + base [ i + key_len ] as u64 ; let right = ( base [ i ] as u64 ) * t ; while left < right { left += M ; } base_h = left - right ; base_h %= M ; } } ); ret }