#include #include #include #include using namespace std; typedef complex C; void fft(vector &f, int n, int dir) { if (n == 1) return; vector f0, f1; for (int i = 0; i < n; i++) { if (i % 2 == 0) { f0.push_back(f[i]); } else { f1.push_back(f[i]); } } fft(f0, n / 2, dir); fft(f1, n / 2, dir); C now = C(1.0, 0); C zeta = polar(1.0, 2 * acos(-1) * dir / n); for(int i = 0; i < n; i++) { f[i] = f0[i % (n / 2)] + now * f1[i % (n / 2)]; now *= zeta; } } vector comb(vector A, vector B) { int size = A.size() + B.size(); int n = 1; while(n < size) n <<= 1; A.resize(n); B.resize(n); fft(A, n, 1); fft(B, n, 1); vector ret; for(int i = 0; i < n; i++) { ret.push_back(A[i] * B[i]); } fft(ret, n, -1); for(int i = 0; i < n; i++) { ret[i] /= n; } return ret; } int solve(string &A, string &B) { int N = A.size(), M = B.size(); vector cnt(N + M); for(char c = 'A'; c <= 'Z'; c++) { vector S(N), T(M); for(int k = 0; k < N; k++) { S[k] = C((A[k] == c), 0); } for(int k = 0; k < M; k++) { T[k] = C((B[k] == c), 0); } reverse(T.begin(), T.end()); vector ret = comb(S, T); for(int k = 0; k < N + M; k++) { cnt[k] += (int)(real(ret[k]) + 0.1); } } int ret = 0; for(int k = 0; k < N + M; k++) { if (cnt[k] == B.size()) { ret++; } } return ret; } void solve() { string s; cin >> s; int N; cin >> N; int ans = 0; for (int i = 0; i < N; i++) { string t; cin >> t; ans += solve(s, t); } cout << ans << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); solve(); return 0; }