/* * Author: srtry * Created: 2025-09-23T00:46:59+09:00 * Coding: utf-8-unix */ use proconio::input; use proconio::marker::Chars; use std::{io::{stdout, BufWriter, Write}}; const pow26:[usize;10] = [ 1, 26, 676, 17576, 456976, 11881376, 308915776, 8031810176, 208827064576, 5429503678976 ]; fn my_hash(arg:&Vec) -> usize { let mut hash_:usize = 0; for (i,&ch) in arg.iter().enumerate() { let tmp:usize = ((ch.clone() as u8) - b'A') as usize; hash_ += tmp * pow26[i]; } hash_ } fn main() { input!{ s:Chars, m:usize, c:[Chars;m] } let out = stdout(); let mut out = BufWriter::new(out.lock()); let mut roll_hashes:[usize;10] = [0;10]; for i in 1..=10 { if i<=s.len(){ let tmp:Vec = (s[..i]).iter().cloned().collect::>(); roll_hashes[i-1] = my_hash(&tmp); } } let mut ans:usize = 0; for c_elem in c.iter() { if c_elem.len() > s.len() { continue; } // 検索文字列のハッシュ計算 let c_hash:usize = my_hash(&c_elem); let mut roll_hash:usize = 26*roll_hashes[c_elem.len()-1]; let mut pre_top_hash:usize = 0; let mut last_hash:usize = 0; for i in 0..s.len()-c_elem.len()+1{ roll_hash = (roll_hash - pre_top_hash)/26 + (last_hash*pow26[c_elem.len()-1]); if roll_hash == c_hash { ans += 1; } pre_top_hash = ((s[i] as u8) - b'A') as usize; if i+c_elem.len() < s.len(){ last_hash = ((s[i+c_elem.len()] as u8) - b'A') as usize}; } } write!(out, "{}", ans).unwrap(); }