#include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; const ll MOD = 1000000007LL; class KMP { string pattern; vector fail; void init(const string &p) { pattern = p; int m = pattern.size(); fail.assign(m + 1, -1); for (int i = 0, j = -1; i < m; i++) { while (j >= 0 && pattern[i] != pattern[j]) j = fail[j]; fail[i + 1] = ++j; } } public: KMP(const string &p) { init(p); } int period(int i) { return i - fail[i]; } vector match(const string &s) { int n = s.size(); int m = pattern.size(); vector res; for (int i = 0, k = 0; i < n; i++) { while (k >= 0 && s[i] != pattern[k]) k = fail[k]; k++; if (k == m) res.push_back(i - m + 1); } return res; } }; int main() { string s; cin >> s; int m; cin >> m; int ans = 0; for (int i = 0; i < m; i++) { string pattern; cin >> pattern; KMP kmp(pattern); vector res = kmp.match(s); ans += res.size(); } cout << ans << "\n"; return 0; }