#include using namespace std; // #include // #include // #include // using namespace __gnu_pbds; // #include // namespace mp = boost::multiprecision; #include using namespace atcoder; // https://atcoder.github.io/ac-library/production/document_ja/ typedef long long int ll; typedef long double ld; const ll mod = 1e9+7; const ll INF = 9'223'372'036'854'775'807/10; #define rep(i,n) for (ll i = 0; i < (n); ++i) #define Rep(i,a,n) for (ll i = (a); i < (n); ++i) #define All(a) (a).begin(),(a).end() #define Pi acos(-1) using V = vector; using P = pair; vector dx = {1, 0, -1, 0, 1, 1, -1, -1}; vector dy = {0, 1, 0, -1, 1, -1, 1, -1}; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b >; struct IoSetup { IoSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << setprecision(15) << fixed; } } iosetup; void printvec(vector a) { for(ll i = 0; i < a.size(); i++) { cout << a[i] << ' '; } cout << '\n'; } /* Rolling Hash 使い方 RollingHash rh(); auto s_hash = rh.build(s); rh.query(s_hash, l, r) // s[l, r)のハッシュ値 rh.combine(h1, h2, h2_len) // h1の後ろにh2を連結したときのハッシュ値 rh.lcp(s_hash, s_l, s_r, t_hash, t_l, t_r) // s[s_l, s_r)とt[t_l, t_r)の最長共通接頭辞の長さ 計算量 build() : O(|S|) query(), combine() : O(1) lcp() : O(log|S|) https://ei1333.github.io/library/string/rolling-hash.hpp */ struct RollingHash { static constexpr uint64_t mod = (1ull << 61ull) - 1; vector power; const uint64_t base; static inline uint64_t add(uint64_t a, uint64_t b) { uint64_t res = a + b; if (res >= mod) res -= mod; return res; } 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) { int sz = (int)s.size(); vector hash(sz + 1); for (int i = 0; i < sz; i++) { hash[i+1] = add(mul(hash[i], base), s[i]); } return hash; } uint64_t query(const vector &hash, int l, int r) { expand(r - l); return add(hash[r], mod - mul(hash[l], power[r - l])); } uint64_t combine(uint64_t h1, uint64_t h2, size_t h2_len) { expand(h2_len); return add(mul(h1, power[h2_len]), h2); } int lcp(const vector &s_hash, int s_l, int s_r, const vector &t_hash, int t_l, int t_r) { int len = min(s_r - s_l, t_r - t_l); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) >> 1; if (query(s_hash, s_l, s_l + mid) == query(t_hash, t_l, t_l + mid)) low = mid; else high = mid; } return low; } }; int main() { string s; cin >> s; RollingHash rh; auto s_hash = rh.build(s); ll s_size = s.size(); ll q; cin >> q; ll ans = 0; while (q--) { string t; cin >> t; auto t_hash = rh.build(t); ll t_size = t.size(); if (s_size < t_size) { continue; } for (ll i = 0; i <= s_size - t_size; i++) { if (rh.query(s_hash, i, i + t_size) == rh.query(t_hash, 0, t_size)) { ans++; } } } cout << ans << '\n'; }