#include using namespace std; //aの中からbに合致するものの最初のindexのvectorを返す int rolling_hash(string &a, string &b){ using lll = __int128_t; const lll base = 591591593, mod = (1ll<<61) - 1; lll basem = 1; int n = a.size(), m = b.size(); lll t = m, u = base; t--; while (t) { if (t & 1) basem = (basem * u) % mod; u = (u * u) % mod; t >>= 1; } lll hash_a = 0, hash_b = 0; for (auto x : b){ hash_b *= base; hash_b += (lll)(x) + 127; hash_b %= mod; } for (int i = 0; i < m; i++){ hash_a *= base; hash_a += (lll)(a[i]) + 127; hash_a %= mod; } int pos = 0; if (hash_a == hash_b) pos++; for (int i = 0; i < n - m; i++){ hash_a -= basem * ((lll)(a[i]) + 127); hash_a *= base; hash_a += ((lll)(a[i + m]) + 127) + mod; hash_a = ((hash_a % mod) + mod) % mod; if (hash_a == hash_b) pos++; } return pos; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); string s; cin >> s; int m; cin >> m; int ans = 0; for (int i = 0; i < m; i++){ string c; cin >> c; ans += rolling_hash(s, c); } cout << ans << endl; }