#pragma region Macros #include #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(a) (a).begin(), (a).end() #define SZ(x) ((int)(x).size()) #define IN(x, a, b) x >= a and x < b using namespace std; using ll = long long; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } template constexpr T INF = numeric_limits::max() / 2; #pragma endregion int main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int M; cin >> M; int ans = 0; constexpr ll BASE = 26; const unordered_map HASH = { {'A', 0}, {'B', 1}, {'C', 2}, {'D', 3}, {'E', 4}, {'F', 5}, {'G', 6}, {'H', 7}, {'I', 8}, {'J', 9}, {'K', 10}, {'L', 11}, {'M', 12}, {'N', 13}, {'O', 14}, {'P', 15}, {'Q', 16}, {'R', 17}, {'S', 18}, {'T', 19}, {'U', 20}, {'V', 21}, {'W', 22}, {'X', 23}, {'Y', 24}, {'Z', 25}}; REP(i, M) { string C; cin >> C; if (SZ(C) > SZ(S)) { continue; } ll hash_q = 0; REP(n, SZ(C)) { ll m = SZ(C) - n - 1; hash_q += HASH.at(C[n]) * pow(BASE, m); } ll hash = 0; REP(n, SZ(C)) { ll m = SZ(C) - n - 1; hash += HASH.at(S[n]) * pow(BASE, m); } if (hash == hash_q) { ans++; } char prev = S[0]; FOR(j, 1, SZ(S) - SZ(C) + 1) { hash -= HASH.at(prev) * pow(BASE, SZ(C) - 1); hash *= BASE; hash += HASH.at(S[j + SZ(C) - 1]); prev = S[j]; if (hash == hash_q) { ans++; } } } cout << ans << endl; return 0; }