#include #include #include #include #include #include #include #include using namespace std; string s,target; bool fin[50001]; vectorHash[50001]; int rolling_hash(int size, long long val) { int cnt = 0; if (fin[size]) { for (int i = 0; i < Hash[size].size(); i++) { if (Hash[size][i] == val)cnt++; } } else { long long hash = 0; for (int j = 0; j < size; j++) hash += (s[j] - 'A')*pow(26, j); if (hash == val)cnt++; Hash[size].push_back(hash); for (int j = size; j < s.size(); j++) { hash -= s[j - size] - 'A'; hash /= 26; hash += (s[j] - 'A')*pow(26, size - 1); if (hash == val)cnt++; Hash[size].push_back(hash); } fin[size] = true; } return cnt; } int main() { cin >> s; int m; cin >> m; int ans = 0; for (int i = 0; i < m; i++) { cin >> target; if (target.size() > s.size())continue; long long target_hash=0; for (int j = 0; j < target.size(); j++) target_hash += (target[j] - 'A')*pow(26, j); ans += rolling_hash(target.size(), target_hash); } cout << ans << endl; return 0; }