#include using namespace std; namespace { typedef double real; typedef long long ll; template ostream& operator<<(ostream& os, const vector& vs) { if (vs.empty()) return os << "[]"; auto i = vs.begin(); os << "[" << *i; for (++i; i != vs.end(); ++i) os << " " << *i; return os << "]"; } template istream& operator>>(istream& is, vector& vs) { for (auto it = vs.begin(); it != vs.end(); it++) is >> *it; return is; } struct KMP { string s; vector PMA; KMP(const string &s) : s(s) { buildPMA(s); } /* t縺ォ蜷ォ縺セ繧後ks縺ョ謨ー繧呈焚縺医k. * 縺薙・螳溯」・〒縺ッ * s = "ABA", * t = "ABABA" * 縺ョ縺ィ縺・ ( [0, 3), [2, 5)縺ァ繝槭ャ繝・) 繧定ソ斐☆. * [2, 5)縺ァ繝槭ャ繝√&縺帙◆縺上↑縺代l縺ーbuildPMA縺ァPMA[M]繧・縺ォ縺励※縺翫¥. */ int match(const string& t) { int N = t.size(), M = s.size(); int Count = 0; int si = 0, ti = 0; while (ti < N) { if (s[si] == t[ti]) { si++; ti++; } else { if (si == 0) ti++; si = PMA[si]; } if (si == M) { Count++; // [ti - M, ti)縺ァ繝槭ャ繝・ si = PMA[si]; } } return Count; } /* Pattern Matching Automaton 繧剃ス懊k */ void buildPMA(const string& s) { int M = s.size(); PMA.resize(M + 1); PMA[0] = 0; PMA[1] = 0; for (int i = 2; i <= M; i++) { int j = PMA[i - 1]; while (true) { if (s[j] == s[i - 1]) { PMA[i] = j + 1; break; } if (j == 0) { PMA[i] = 0; break; } j = PMA[j]; } } } }; string S; int M; vector C; void input() { cin >> S; cin >> M; C.clear(); C.resize(M); for (int i = 0; i < M; i++) cin >> C[i]; } void solve() { int ans = 0; for (int i = 0; i < M; i++) { const string& c = C[i]; KMP kmp(c); ans += kmp.match(S); } cout << ans << endl; } } int main() { input(); solve(); return 0; }