#include #include #include #include using namespace std; int ans; int table[50001]; void kmp_maketable(string key) { table[0] = -1; table[1] = 0; int i = 2, j = 0; while (i == 0 || key[i - 1]) { if (key[i - 1] == key[j]) { table[i++] = ++j; } else if (j>0) { j = table[j]; } else { table[i++] = 0; } } } void kmp_search(string str, string key) { int i = 0, j = 0; while (str[i]) { if (str[i] == key[j]) { if (!key[j + 1]) { ans++; } i++, ++j; } else if (j>0) { j = table[j]; } else { i++; } } } int main() { string s; cin >> s; int m; cin >> m; for (int i = 0; i < m; i++) { string target; cin >> target; kmp_maketable(target); kmp_search(s, target); } cout << ans << endl; return 0; }