#include using namespace std; #define BE(x) x.begin(), x.end() using ll = long long; template using vec = vector; class rolling_hash { private: using ull = uint64_t; static const ull max_a = 127ull; // set the max value of sequence to be hashed static constexpr ull p = (1ull<<61)-1ull; static const ull p_root = 37ull; static const int base_n = 2; // number of bases static ull base[base_n]; static vector base_pow[base_n]; vector hash[base_n]; ull mod(ull x) { ull res = (x>>61) + (x&p); if (res >= p) res -= p; return res; } ull mul(ull a, ull b) { constexpr ull mask31 = (1ull<<31)-1ull; constexpr ull mask30 = (1ull<<30)-1ull; const ull au = a>>31; const ull bu = b>>31; const ull ad = a&mask31; const ull bd = b&mask31; const ull mid = au*bd + bu*ad; const ull midu = mid>>30; const ull midd = mid&mask30; return mod(au*bu*2ull + midu+(midd<<31) + ad*bd); } ull root_pow(ull ex) { ull res = 1ull; ull bin = p_root; while (ex) { if (ex&1ull) res = mul(res, bin); bin = mul(bin, bin); ex >>= 1; } return res; } void set_base() { random_device rd; mt19937_64 rand(rd()); for (ull &e : base) { while (!e) { const ull ex = rand(); if (gcd(ex, p-1ull) != 1ull) continue; const ull b = root_pow(ex); if (b <= max_a+1ull) continue; if (find(base, base+base_n, b) != base+base_n) continue; e = b; } } } void set_base_pow(const int n) { const int prev_size = base_pow[0].size(); for (int i = 0; i < base_n; ++i) { base_pow[i].resize(n); base_pow[i][0] = 1ull; for (int j = prev_size+1; j < n; ++j) { base_pow[i][j] = mul(base_pow[i][j-1], base[i]); } } } public: template rolling_hash(T arr) { if (!base[0]) set_base(); const int n = arr.size(); if (base_pow[0].size() < (size_t)n) set_base_pow(n+1); for (int i = 0; i < base_n; ++i) { hash[i].resize(n+1); hash[i][0] = 0ull; for (int j = 0; j < n; ++j) { hash[i][j+1] = mod(mul(hash[i][j],base[i])+(ull)arr[j]+1ull); } } } vector subseq(int l, int r) { // 0-indexed, hankai-kukan vector res; for (int i = 0; i < base_n; ++i) { ull h = hash[i][r] + p-mul(hash[i][l],base_pow[i][r-l]); if (h >= p) h -= p; res.push_back(h); } return res; } }; uint64_t rolling_hash::base[]; vector rolling_hash::base_pow[]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; int m; cin >> s >> m; int n = s.size(); rolling_hash sh(s); int c = 0; while (m--) { string t; cin >> t; auto&& th = rolling_hash(t).subseq(0,t.size()); int tn = t.size(); for (int i = 0; i+tn <= n; ++i) { if (sh.subseq(i,i+tn) == th) ++c; } } cout << c << '\n'; }