// https://yukicoder.me/problems/no/430 // ハッシュは文字に数字0を対応させると衝突が起こる(AとAAが同じハッシュになる) // なので必ず1から対応させる #include using namespace std; using ll = long long; using ull = unsigned long long; #define rep0(i,n) for(int i=0; i mp; // ハッシュを計算 ll CalcHash(string pattern){ int p_len = pattern.length(); ll p_hash = 0; rep0(i, p_len){ p_hash += base_n[p_len-1-i] * (ll)(pattern[i] + 1 - 'A'); p_hash %= mod; } return p_hash; } // 部分文字列のハッシュをすべて管理するmapを作る void MakeRollingHashMap(string text){ int t_len = text.length(); rep1(len, min(10, t_len)){ ll t_hash = 0; rep0(i, len){ t_hash += base_n[len-1-i] * (ll)(text[i] + 1 - 'A'); t_hash %= mod; } mp[t_hash] += 1; // 先頭文字でforを回してt_hashを更新していく for(int i=1; i<=t_len-len; ++i){ ll new_hash = (base * t_hash) % mod; new_hash = (new_hash - base_n[len] * (text[i-1] + 1 - 'A') + mod) % mod; new_hash += (text[i + len - 1] + 1 - 'A'); new_hash %= mod; t_hash = new_hash; mp[t_hash] += 1; } } } int main(){ string S; cin >> S; int M; cin >> M; rep0(i, 11) base_n[i] = powpowm(base, i); MakeRollingHashMap(S); int ans = 0; rep1(i, M){ string C; cin >> C; ll hsh = CalcHash(C); if(mp.count(hsh)) ans += mp[hsh]; } cout << ans << endl; }