#include using namespace std; template //aの中からbに合致するものの最初のindexのvectorを返す vector get_rolling_hash(vector &a, vector &b){ using lll = __int128_t; const lll base = 591591593, mod = (1ll<<61) - 1, safe = 127; 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 = (hash_b * base + (lll)x + safe) % mod; } for (int i = 0; i < m; i++){ hash_a = (hash_a * base + (lll)a[i] + safe) % mod; } vector pos; if (hash_a == hash_b) pos.push_back(0); for (int i = 0; i < n - m; i++){ hash_a = (((hash_a - basem * ((lll)(a[i]) + safe)) % mod + mod) * base + (lll)(a[i + m]) + safe) % mod; if (hash_a == hash_b) pos.push_back(i + 1); } return pos; } template //aの中からbに合致するものの最初のindexのvectorを返す int rolling_hash(vector &a, vector &b){ using lll = __int128_t; const lll base = 26, mod = (1ll<<61) - 1, safe = 0; 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 = (hash_b * base + (lll)x + safe) % mod; } for (int i = 0; i < m; i++){ hash_a = (hash_a * base + (lll)a[i] + safe) % mod; } int pos = 0; if (hash_a == hash_b) pos++; for (int i = 0; i < n - m; i++){ hash_a = (((hash_a - basem * ((lll)(a[i]) + safe)) % mod + mod) * base + (lll)(a[i + m]) + safe) % mod; if (hash_a == hash_b) pos++; } return pos; } vector get_rolling_hash(string &s, string &t){ vector a(s.size()), b(t.size()); for (int i = 0; i < (int)s.size(); i++){ a[i] = s[i]; } for (int i = 0; i < (int)t.size(); i++){ b[i] = t[i]; } return get_rolling_hash(a, b); } int rolling_hash(string &s, string &t){ vector a(s.size()), b(t.size()); for (int i = 0; i < (int)s.size(); i++){ a[i] = s[i]; } for (int i = 0; i < (int)t.size(); i++){ b[i] = t[i]; } return rolling_hash(a, b); } int main(){ 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; }