#include #include #include using namespace std; vector kmp(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; } vector matches(text.size(), false); 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()) { matches[j - i] = true; i = kmp_next[i]; } } return matches; }; int main() { string s; cin >> s; int m; cin >> m; int ans = 0; while (m--) { string t; cin >> t; vector matches = kmp(t, s); ans += accumulate(matches.begin(), matches.end(), 0); } cout << ans << endl; }