#include using namespace std; using hash_value = pair, string>; class rolling_hash{ mt19937 mt; const uint32_t p[3] = {2111511013, 2131131137, 2147483647}; uint64_t b[3]; uint64_t mpow(uint64_t x, uint64_t y, uint32_t m){ if(y == 0) return 1; if(y == 1) return x%m; if(y%2 == 0) return mpow(x*x%m, y/2, m); return mpow(x*x%m, y/2, m) * x % m; } public: rolling_hash(){ random_device rd; mt.seed(rd()); for(int i=0;i<3;i++){ b[i] = 0; while(!b[i]) b[i] = mt() % p[i]; } } hash_value operator()(string s){ vector h = {0, 0, 0}; for(char c : s){ for(int i=0;i<3;i++) h[i] = (h[i]*b[i]%p[i]+c) % p[i]; } return {h, s}; } void push_back(hash_value &hvl, char c){ auto &hv = hvl.first; for(int i=0;i<3;i++) hv[i] = (hv[i]*b[i]%p[i]+c) % p[i]; hvl.second.push_back(c); } void push_front(hash_value &hvl, char c){ auto &hv = hvl.first; for(int i=0;i<3;i++) hv[i] = (hv[i] + mpow(b[i], hvl.second.size(), p[i])*c%p[i]) % p[i]; hvl.second = c + hvl.second; } void pop_back(hash_value &hvl){ auto &hv = hvl.first; for(int i=0;i<3;i++) hv[i] = (hv[i]+p[i]-hvl.second.back())%p[i] * mpow(b[i], p[i]-2, p[i]) % p[i]; hvl.second.pop_back(); } void pop_front(hash_value &hvl){ auto &hv = hvl.first; for(int i=0;i<3;i++) hv[i] = (hv[i] + p[i] - hvl.second[0]*mpow(b[i], hvl.second.size()-1, p[i])%p[i]) % p[i]; hvl.second.erase(hvl.second.begin()); } }; bool operator==(const hash_value &a, const hash_value &b){ return a.first == b.first; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout.precision(12); cout.setf(ios_base::fixed, ios_base::floatfield); string s; int m; string c[5000]; cin >> s; cin >> m; for(int i=0;i> c[i]; rolling_hash rh; hash_value hash_s, hash_c; int ans = 0; for(int i=0;i