#include #include #include using namespace std; vector bnxt(const string &pat) { int m = pat.size(); vector nxt(m, 0); int j = 0; for (int i = 1; i < m; i++) { while (j && pat[i] != pat[j]) j = nxt[j - 1]; if (pat[i] == pat[j]) j++; nxt[i] = j; } return nxt; } int kmp(const string &txt, const string &pat) { int n = txt.size(), m = pat.size(); if (m == 0) return 0; vector nxt = bnxt(pat); int cnt = 0, j = 0; for (int i = 0; i < n; i++) { while (j && txt[i] != pat[j]) j = nxt[j - 1]; if (txt[i] == pat[j]) j++; if (j == m) { cnt++; j = nxt[j - 1]; } } return cnt; } int main() { ios::sync_with_stdio(false); string rope; getline(cin, rope); int t; cin >> t; int ans = 0; while (t--) { string knot; getline(cin, knot); ans += kmp(rope, knot); } cout << ans << "\n"; return 0; }