#include #include #include #include #include #include #include #include #include #include #include #include using ll = long long int; using namespace std; long long int count_contain(std::string a, std::string b, unsigned long long hash_base); int main(){ string S, strtmp; ll M; vector C; cin >> S; cin >> M; for(ll i = 0; i < M; i++){ cin >> strtmp; C.push_back(strtmp); } ll ans = 0; for(ll i = 0; i < M; i++){ ans += count_contain(C[i], S, 13); cerr << ans << endl; } cerr << "Answer:" << endl; cout << ans << endl; return 0; } // if b[i,i+a_len) = a then return i (i >= 0) // else return -1 long long int count_contain(std::string a, std::string b, unsigned long long hash_base){ // get length of a and b long long int a_len = a.length(); long long int b_len = b.length(); // if a is longer than b if(a_len > b_len){ return 0; } // calculate hash_a unsigned long long hash_a = 0; for(long long int i = 0; i < a_len; i++){ hash_a = hash_a*hash_base + a[i]; } // solve problem unsigned long long hash_b = 0; unsigned long long tmp = 1; long long int ans = 0; for(long long int i = 0; i < a_len; i++){ hash_b = hash_b*hash_base + b[i]; tmp *= hash_base; } if(hash_a == hash_b){ ans++; } for(long long int i = 1; i <= b_len - a_len; i++){ hash_b = hash_b*hash_base + b[i+a_len-1] - tmp*b[i-1]; if(hash_b == hash_a){ ans++; } } return ans; }