#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; string a, b; vector pi; int res = 0; void kmp() { int j = 0; for (int i = 0; i < a.length(); i++) { while (j > 0 && a[i] != b[j]) { j = pi[j - 1]; } if (a[i] == b[j]) { if (j == b.length() - 1) { res++; j = pi[j]; } else { j++; } } } } void getpi() { pi.clear(); pi.resize(b.length()); int j = 0; for (int i = 1; i < b.length(); i++) { while (j > 0 && b[i] != b[j]) { j = pi[j - 1]; } if (b[i] == b[j]) { pi[i] = ++j; } } } int main(void) { cin.tie(0); ios::sync_with_stdio(false); long long int ans = 0; int n; cin >> a; cin >> n; for (int i = 0; i < n; i++) { cin >> b; getpi(); kmp(); } cout << res << '\n'; return 0; }