#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const long long INF = 1LL << 60; const long long MOD = 1000000007LL; const long long MAX = 500000LL; using namespace std; typedef unsigned long long ull; typedef long long ll; class RollingHash { public: typedef long long int_type; typedef pair hash_type; int_type base1; int_type base2; int_type mod1; int_type mod2; vector hash1; vector hash2; vector pow1; vector pow2; RollingHash() : base1(1009), base2(1007), mod1(1000000007), mod2(1000000009) {} void init(const string &s) { ll n = s.size(); hash1.assign(n + 1, 0); hash2.assign(n + 1, 0); pow1.assign(n + 1, 1); pow2.assign(n + 1, 1); for (ll i = 0; i < n; i++) { hash1[i + 1] = (hash1[i] * base1 + s[i]) % mod1; hash2[i + 1] = (hash2[i] * base2 + s[i]) % mod2; pow1[i + 1] = pow1[i] * base1 % mod1; pow2[i + 1] = pow2[i] * base2 % mod2; } } hash_type get(ll l, ll r) { int_type t1 = ((hash1[r] - hash1[l] * pow1[r - l]) % mod1 + mod1) % mod1; int_type t2 = ((hash2[r] - hash2[l] * pow2[r - l]) % mod2 + mod2) % mod2; return make_pair(t1, t2); } void add(string &t) { ll old_len = hash1.size(); hash1.resize(old_len + t.size()); hash2.resize(old_len + t.size()); pow1.resize(hash1.size()); pow2.resize(hash1.size()); for (ll i = 0; i < t.size(); i++) { hash1[old_len + i] = (hash1[old_len + i - 1] * base1 + t[i]) % mod1; hash2[old_len + i] = (hash2[old_len + i - 1] * base2 + t[i]) % mod2; pow1[old_len + i] = pow1[old_len + i - 1] * base1 % mod1; pow2[old_len + i] = pow2[old_len + i - 1] * base2 % mod2; } } }; int main() { string s; cin >> s; RollingHash rol1; rol1.init(s); ll M; cin >> M; ll cnt = 0; for (ll i = 0; i < M; i++) { string c; cin >> c; RollingHash rol2; rol2.init(c); for (ll j = 0; j <= (ll)s.size() - (ll)c.size(); j++) { if (rol1.get(j, j + c.size()) == rol2.get(0, c.size())) { cnt++; } } } cout << cnt << endl; return 0; }