#include #define rep(i,n,m) for(int i = (n); i <(m); i++) #define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--) using namespace std; using ll = long long; int kmp_search(string ref, string key) { vector index(key.size(), 0); int i, j; i = 0, j = 1; while (j < key.size()) { if (key[i] == key[j]) { ++i; index[j] = i; ++j; } else if (i == 0) { index[j] = 0; ++j; } else i = index[i-1]; // cout << "a : " << i << ' ' << j << ' ' << key << endl; } i = j = 0; int cnt = 0; while (i < ref.size()) { if (ref[i] == key[j]) ++i, ++j; else if (j == 0) ++i; else j = index[j-1]; if (j == key.size()) ++cnt, j = index[j-1]; // cout << "b : " << i << ' ' << j << ' ' << key << endl; } // cout << cnt << endl; return cnt; } int main() { string s; int m; cin >> s >> m; int cnt = 0; rep(i, 0, m) { string key; cin >> key; cnt += kmp_search(s, key); // cout << kmp_search(s, key) << endl; } cout << cnt << endl; return 0; }