#include using namespace std; using hash_value = pair, size_t>; 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.size()}; } 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++; } 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, p[i])*c%p[i]) % p[i]; hvl.second++; } void pop_back(hash_value &hvl, char c){ auto &hv = hvl.first; for(int i=0;i<3;i++) hv[i] = (hv[i]+p[i]-c%p[i]) * mpow(b[i], p[i]-2, p[i]) % p[i]; hvl.second--; } void pop_front(hash_value &hvl, char c){ auto &hv = hvl.first; for(int i=0;i<3;i++) hv[i] = (hv[i] + p[i] - c*mpow(b[i], hvl.second-1, p[i])%p[i]) % p[i]; hvl.second--; } }; 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