#include using namespace std; struct RollingHash { static const uint64_t mod = (1ull << 61ull) - 1; using uint128_t = __uint128_t; vector power; const uint64_t base; static inline uint64_t add(uint64_t a, uint64_t b) { if ((a += b) >= mod) a -= mod; return a; } static inline uint64_t mul(uint64_t a, uint64_t b) { uint128_t c = (uint128_t)a * b; return add(c >> 61, c & mod); } static inline uint64_t generate_base() { mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution rand(1, RollingHash::mod - 1); return rand(mt); } inline void expand(size_t sz) { if (power.size() < sz + 1) { int pre_sz = (int)power.size(); power.resize(sz + 1); for (int i = pre_sz - 1; i < sz; i++) { power[i + 1] = mul(power[i], base); } } } explicit RollingHash(uint64_t base = generate_base()) : base(base), power{1} {} vector build(const string &s) const { int sz = s.size(); vector hashed(sz + 1); for (int i = 0; i < sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } template vector build(const vector &s) const { int sz = s.size(); vector hashed(sz + 1); for (int i = 0; i < sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } uint64_t query(const vector &s, int l, int r) { expand(r - l); return add(s[r], mod - mul(s[l], power[r - l])); } uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) { expand(h2len); return add(mul(h1, power[h2len]), h2); } int lcp(const vector &a, int l1, int r1, const vector &b, int l2, int r2) { int len = min(r1 - l1, r2 - l2); int low = 0, high = len + 1; while (high - low > 1) { int mid = (low + high) / 2; if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) low = mid; else high = mid; } return low; } }; int main() { string s; cin >> s; RollingHash rh; auto rh1 = rh.build(s); int m; cin >> m; int ans = 0; for (int i = 0; i < m; i++) { string c; cin >> c; auto rh2 = rh.build(c); for (int j = 0; j + c.size() <= s.size(); j++) { if (rh.query(rh1, j, j + c.size()) == rh.query(rh2, 0, c.size())) { ans++; } } } cout << ans << endl; }