#include #include #include #include #include #include #include #include using namespace std; #define GET_ARG(a,b,c,F,...) F #define REP3(i,s,e) for (i = s; i <= e; i++) #define REP2(i,n) REP3 (i,0,(int)(n)-1) #define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__) #define RREP3(i,s,e) for (i = s; i >= e; i--) #define RREP2(i,n) RREP3 (i,(int)(n)-1,0) #define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__) #define DEBUG(x) cerr << #x ": " << x << endl typedef long long ll; ll pow(ll x, int n) { ll ret = 1; while (n) { if (n % 2) ret *= x; x *= x; n /= 2; } return ret; } int main(void) { int m; string s; cin >> s >> m; int ans = 0; while (m--) { string t; cin >> t; ll hash = 0; for (auto c: t) { hash = hash * 26 + c - 'A'; } ll h = 0; int i; REP (i,min(s.size(),t.size())) { h = h * 26 + s[i] - 'A'; } if (h == hash) ans++; ll x = pow(26,t.size()-1); REP (i,t.size(),s.size()) { h = (h - (s[i-t.size()] - 'A') * x) * 26 + s[i] - 'A'; if (h == hash) ans++; } } cout << ans << endl; return 0; }