use std::collections::BTreeMap; pub static MOD1:u64 = 1000000021; pub static B1:u64 = 10000; // pub static MOD2:u64 = 1000000033; pub static B2:u64 = 10009; fn main(){ let mut sc = Scanner::new(); while sc.ok() { let s:Vec = sc.next::().chars() .map(|x| x as u64).collect(); let mut mp = BTreeMap::new(); let pow1:Vec<_> = (0..20).map(|x| modpow(B1, x)).collect(); let pow2:Vec<_> = (0..20).map(|x| modpow(B2, x)).collect(); for l in 1..11 { let mut h1 = 0; let mut h2 = 0; for i in 0..s.len() { h1 = (h1 * B1 + s[i]) % MOD1; h2 = (h2 * B2 + s[i]) % MOD1; if i >= l-1 { *mp.entry(h1 << 32 | h2).or_insert(0) += 1; h1 = (h1 + MOD1 - s[i+1-l] * pow1[l-1] % MOD1) % MOD1; h2 = (h2 + MOD1 - s[i+1-l] * pow2[l-1] % MOD1) % MOD1; } } } let m = sc.next(); let mut ans:u64 = 0; for _ in 0..m { let s:Vec<_> = sc.next::().chars() .map(|x| x as u64).collect(); let h1 = s.iter().fold(0, |acc, x| (acc * B1 + x) % MOD1); let h2 = s.iter().fold(0, |acc, x| (acc * B2 + x) % MOD1); let x = mp.get(&(h1 << 32 | h2)).or(Some(&0)).unwrap().clone(); ans += x; } println!("{}", ans); } } fn modpow(x: u64, y: u64) -> u64 { if y == 0 { 1 } else if y%2 == 1 { x * modpow(x, y-1) % MOD1 } else { let t = modpow(x, y/2); t * t % MOD1 } } #[allow(dead_code)] struct Scanner { token_buffer: Vec, index: usize } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { token_buffer: vec![], index: 0 } } fn next(&mut self) -> T where T: std::str::FromStr { self.wrapped::().unwrap() } fn wrapped(&mut self) -> Option where T: std::str::FromStr { self.get_token().and_then(|s| s.parse::().ok()) } fn ok(&mut self) -> bool { !self.eof() } fn eof(&mut self) -> bool { !self.read_line() || self.index >= self.token_buffer.len() } fn get_token(&mut self) -> Option<&String> { if !self.read_line() { None } else { self.index += 1; Some(&self.token_buffer[self.index - 1]) } } fn read_line(&mut self) -> bool { while self.index >= self.token_buffer.len() { let mut st = String::new(); while st.trim() == "" { match std::io::stdin().read_line(&mut st) { Ok(l) if l > 0 => continue, _ => return false } } self.token_buffer = st.split_whitespace() .map(|x| x.to_string()).collect(); self.index = 0; } true } }