#include #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using pii = pair; using vi = vector; template ostream& operator<<(ostream& os, const vector& v) { os << "sz=" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = 1e9 + 7; template constexpr T INF = numeric_limits::max() / 100; template (1000000007), HashType mod2 = static_cast(1000000009), HashType add1 = static_cast(1000010007), HashType add2 = static_cast(1003333331)> class RollingHash { public: static constexpr HashType MOD1 = mod1; static constexpr HashType MOD2 = mod2; using T = HashType; RollingHash(const Container& original) : size(original.size()), mt{random_device{}()}, base1{getRand1()}, base2{getRand2()}, pow1(size + 1, 1), pow2(size + 1, 1), accum_hash1(size + 1, 0), accum_hash2(size + 1, 0) { for (int i = 1; i <= size; i++) { pow1[i] = (pow1[i - 1] * base1) % mod1; accum_hash1[i] = (accum_hash1[i - 1] * base1 + add1 + static_cast(original[i - 1])) % mod1; } for (int i = 1; i <= size; i++) { pow2[i] = (pow2[i - 1] * base2) % mod2; accum_hash2[i] = (accum_hash2[i - 1] * base2 + add2 + static_cast(original[i - 1])) % mod2; } } RollingHash(const Container& original, const T base1, const T base2) : size(original.size()), mt{random_device{}()}, base1{base1}, base2{base2}, pow1(size + 1, 1), pow2(size + 1, 1), accum_hash1(size + 1, 0), accum_hash2(size + 1, 0) { for (int i = 1; i <= size; i++) { pow1[i] = (pow1[i - 1] * base1) % mod1; accum_hash1[i] = (accum_hash1[i - 1] * base1 + add1 + static_cast(original[i - 1])) % mod1; } for (int i = 1; i <= size; i++) { pow2[i] = (pow2[i - 1] * base2) % mod2; accum_hash2[i] = (accum_hash2[i - 1] * base2 + add2 + static_cast(original[i - 1])) % mod2; } } pair getHash(const int l, const int r) const // [l,r) { const T h1 = (((accum_hash1[r] - accum_hash1[l] * pow1[r - l]) % mod1) + mod1) % mod1; const T h2 = (((accum_hash2[r] - accum_hash2[l] * pow2[r - l]) % mod2) + mod2) % mod2; return make_pair(h1, h2); } private: T getRand1() { static uniform_int_distribution dist{2, mod1 - 1}; return dist(mt); } T getRand2() { static uniform_int_distribution dist{2, mod2 - 1}; return dist(mt); } const int size; mt19937 mt; const T base1; const T base2; vector pow1; vector pow2; vector accum_hash1; vector accum_hash2; }; int main() { cin.tie(0); ios::sync_with_stdio(false); mt19937 mt{random_device{}()}; constexpr ll mod1 = 1000000007; constexpr ll mod2 = 1000000009; uniform_int_distribution d1{2, mod1 - 1}; uniform_int_distribution d2{2, mod2 - 1}; const ll base1 = d1(mt); const ll base2 = d2(mt); string s; cin >> s; RollingHash s_hash(s, base1, base2); int M; cin >> M; using P = pair; constexpr int SIZE = 10; vector> subs(SIZE + 1); for (int i = 1; i <= SIZE; i++) { for (int j = 0; j + i - 1 < s.size(); j++) { subs[i].insert(s_hash.getHash(j, i + j)); } } int num = 0; for (int i = 0; i < M; i++) { string c; cin >> c; const int sz = c.size(); const P v = RollingHash{c, base1, base2}.getHash(0, sz); if (subs[sz].find(v) != subs[sz].end()) { num++; } } cout << num << endl; return 0; }