#include #include #include #include #include #include #include using namespace std; using ll = long long; struct RollingHash{ static constexpr ll MOD = (1LL << 61)-1; const ll b1; const vector hs; const vector rev; RollingHash(const string &s): b1(rnd()), hs(make_hash(s)), rev(make_revlist(s.size())){ // cerr << Mul(2, 2) << " " << Mul(18695992641856, 18695992641856) << endl; // cerr << Mul(1, 1) << endl; } RollingHash(const string &s, ll b0): b1(b0), hs(make_hash(s)), rev(make_revlist(s.size())){ // cerr << Mul(3, 2) << " " << Mul(18695992641856, 18695992641856) << // " " << mpow(172, MOD-2) << " " << mpow(172, 17) << endl; // cerr << endl; } // hash1(s[l, r)), hash2(s[l, r)) ll get(int l, int r){ return Mul(calcMod(MOD+hs[r]-hs[l]), rev[l]);//(hs[r]-hs[l]+MOD)%MOD*rev[l]%MOD } private: static constexpr ll MASK31 = (1LL << 31)-1; static constexpr ll MASK30 = (1LL << 30)-1; static constexpr ll MASK61 = (1LL << 61)-1; // a*b mod 2^61-1 ll Mul(const ll a, const ll b){ assert(MASK31 > 0); // cerr << a << " " << b << endl; ll au = a >> 31; ll ad = a & MASK31; ll bu = b >> 31; ll bd = b & MASK31; ll mid = ad*bu + au*bd; ll midu = mid >> 30; ll midd = mid & MASK30; /* cerr << a << " " << b << endl; cerr << au << " " << ad << " " << bu << " " << bd << " | " << mid << " " << midu << " " << midd << endl; cerr << (midd << 31) << endl; cerr << calcMod(au*bu*2 + midu + (midd << 31) + ad*bd) << endl; assert(false); */ /* if(calcMod(au*bu*2 + midu + (midd << 31) + ad*bd) == 0 && a != 0 && b != 0){ cerr << a << " * " << b << " = " << calcMod(au*bu*2 + midu + (midd << 31) + ad*bd) << " (" << a*b << ")" << endl; cerr << (1LL & MASK31) << " " << MASK31 << " " << (1LL << 31) << endl; cerr << (a >> 31) << " " << (a & MASK31) << " " << (b >> 31) << " " << (b & MASK31) << endl; cerr << au << " " << ad << " " << bu << " " << bd << " | " << mid << " " << midu << " " << midd << endl; } */ return calcMod(au*bu*2 + midu + (midd << 31) + ad*bd); } // x mod 2^61-1 ll calcMod(ll x){ ll xu = x >> 61; ll xd = x & MASK61; ll res = xu+xd; if(res >= MOD) res -= MOD; // assert(0 <= res && res < MOD); return res; } vector make_hash(const string &s){ vector hs(s.size()+1); hs[0] = 0; ll bm = 1; for(int i = 0; i < s.size(); i++){ hs[i+1] = calcMod(hs[i]+Mul(bm, s[i])); bm = Mul(bm, b1); } return hs; } // 逆元の前計算 vector make_revlist(int n){ vector rev(n); ll bm = 1; // cerr << b1 << " " << bm << " : "; for(int i = 0; i < n; i++){ rev[i] = mpow(bm, MOD-2); // cerr << bm << " " << rev[i] << " "; bm = Mul(bm, b1); } // cerr << endl; return rev; } ll rnd(){ mt19937_64 mt{1ULL * chrono::steady_clock::now().time_since_epoch().count()}; return mt()%(MOD-2)+2; } ll mpow(ll a, ll x){ // assert(0 < a && a < MOD); // cerr << "ok "; ll res = 1; for(; x > 0; x >>= 1){ assert(0 <= a && a < MOD); assert(0 <= res && res < MOD); if(x & 1){ res = Mul(res, a); // res *= a; // res %= MOD; } a = Mul(a, a); // a *= a; // a %= MOD; // cerr << res << " " << a << " "; } // cerr << endl; return res; } }; int main(){ string s; cin >> s; int m; cin >> m; vector c(m); for(auto &it: c) cin >> it; RollingHash hs(s); vector hc; for(auto &it: c) hc.emplace_back(it, hs.b1); // for(int i = 0; i < s.size(); i++) cerr << hs.rev[i] << " "; ll ans = 0; for(int i = 0; i < m; i++){ // cerr << hc[i].get(0, c[i].size()) << " : "; for(int j = 0; j+c[i].size() <= s.size(); j++){ if(hs.get(j, j+c[i].size()) == hc[i].get(0, c[i].size())){ // cerr << hs.get(j, j+c[i].size()) << " "; ans++; } } // cerr << endl; } cout << ans << endl; return 0; }