#include using namespace std; const uint64_t hashmod = 0x1fffffffffffffff; const uint64_t base = chrono::duration_cast(chrono::system_clock::now().time_since_epoch()).count() % hashmod; const uint64_t mdf = uint64_t(1e17) + 1; template struct rolling_hash { int n; vector hash, p; inline uint64_t mul(uint64_t a, uint64_t b) const { uint64_t a31 = a >> 31, b31 = b >> 31; a &= 0x7fffffffull; b &= 0x7fffffffull; uint64_t x = a * b31 + b * a31; uint64_t res = (a31 * b31 << 1) + (x >> 30) + ((x & 0x3fffffffull) << 31) + a * b; res = (res >> 61) + (res & hashmod); if (res >= hashmod) res -= hashmod; return res; } rolling_hash(const T &a) { n = (int)a.size(); hash.assign(n + 1, 0ull); p.assign(n + 1, 0ull); p[0] = 1; for(int i = 0; i < n; i++) { p[i + 1] = mul(p[i], base); hash[i + 1] = mul(hash[i], base) + (mdf + (uint64_t)a[i]); if(hash[i + 1] >= hashmod) hash[i + 1] -= hashmod; } } // get hashing of S[l, r) inline uint64_t get(int l, int r) const { uint64_t res = hash[r] + hashmod - mul(hash[l], p[r - l]); if (res >= hashmod) res -= hashmod; return res; } // return longest common prefixes of a and b inline int lcp(const rolling_hash &b, int l1, int r1, int l2, int r2) const { int size = min(r1 - l1, r2 - l2); int ok = 0, ng = size + 1; while(ng - ok > 1) { int mid = (ok + ng) / 2; if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) ok = mid; else ng = mid; } return ok; } // return hash1 + hash2 inline uint64_t connect(uint64_t hash1, uint64_t hash2, int hash2size) const { uint64_t res = mul(hash1, p[hash2size]) + hash2; if (res >= hashmod) res -= hashmod; return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; rolling_hash h(s); int m; cin >> m; long long ans = 0; for (int i = 0; i < m; i++) { string c; cin >> c; rolling_hash t(c); for (int j = 0; j + c.size() <= (int)s.size(); j++) { if (h.get(j, j+(c.size())) == t.get(0, (int) c.size())) ans++; } } cout << ans << "\n"; }