#include #include #include using namespace std; int kmp_cnt(string& pattern, string& text) { vector kmp_next(pattern.size()+1); kmp_next[0] = -1; for (int i = 0, j = -1; i < pattern.size(); ) { while (j >= 0 && pattern[i] != pattern[j]) j = kmp_next[j]; i++; j++; if (i < pattern.size() && pattern[i] == pattern[j]) kmp_next[i] = kmp_next[j]; else kmp_next[i] = j; } int ans = 0; for (int i = 0, j = 0; j < text.size(); ) { while (i >= 0 && pattern[i] != text[j]) i = kmp_next[i]; i++; j++; if (i == pattern.size()) { ans++; i = kmp_next[i]; } } return ans; }; int main() { string s; cin >> s; int m; cin >> m; int ans = 0; while (m--) { string t; cin >> t; ans += kmp_cnt(t, s); } cout << ans << endl; }