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 suffix_array = SuffixArray::new(s.as_bytes()); let mut cnt = 0; for _ in 0..m { let c: String = iter.next().unwrap().parse::().unwrap(); cnt += suffix_array.count(c.as_bytes()); } println!("{}", cnt); } #[allow(dead_code)] #[derive(Debug)] pub struct SuffixArray<'a> { sa: Vec, base: &'a [u8], } #[allow(dead_code)] impl<'a> SuffixArray<'a> { fn cmp(rank: &[Option], n: usize, k: usize, i: usize, j: usize) -> std::cmp::Ordering { if rank[i] != rank[j] { rank[i].cmp(&rank[j]) } else { let ri = if i + k <= n { Some(rank[i + k]) } else { None }; let rj = if j + k <= n { Some(rank[j + k]) } else { None }; ri.cmp(&rj) } } pub fn new(base: &'a [u8]) -> SuffixArray { let n = base.len(); let mut sa = vec![0usize; n + 1]; let mut rank = vec![None; n + 1]; for i in 0..=n { sa[i] = i; rank[i] = if i < n { Some(base[i] as u64) } else { None }; } { let mut k = 1; while k <= n { sa.sort_by(|&i, &j| SuffixArray::cmp(&rank, n, k, i, j)); let mut tmp = vec![0u64; n + 1]; for i in 1..=n { tmp[sa[i]] = tmp[sa[i - 1]] + (if SuffixArray::cmp(&rank, n, k, sa[i - 1], sa[i]) == std::cmp::Ordering::Less { 1 } else { 0 }); } for i in 0..=n { rank[i] = Some(tmp[i]); } k *= 2; } } SuffixArray { sa: sa, base: base } } pub fn count(&self, key: &[u8]) -> usize { self.upper_bound(key) - self.lower_bound(key) } #[doc = " returns unordered indices"] pub fn find(&self, key: &[u8]) -> Vec { let mut ret = vec![]; for i in self.lower_bound(key)..self.upper_bound(key) { ret.push(self.sa[i]); } ret } #[doc = " lower bound of rank"] pub fn lower_bound(&self, key: &[u8]) -> usize { let mut low = 0; let mut high = self.base.len() + 1; while low != high { let mid = (low + high) / 2; let z = std::cmp::min(self.sa[mid] + key.len(), self.base.len()); match self.base[self.sa[mid]..z].cmp(key) { std::cmp::Ordering::Less => low = mid + 1, _ => high = mid, }; } low } #[doc = " upper bound of rank"] pub fn upper_bound(&self, key: &[u8]) -> usize { let mut low = 0; let mut high = self.base.len() + 1; while low != high { let mid = (low + high) / 2; let z = std::cmp::min(self.sa[mid] + key.len(), self.base.len()); match self.base[self.sa[mid]..z].cmp(key) { std::cmp::Ordering::Greater => high = mid, _ => low = mid + 1, } } low } }