#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(hash(s)), rev(make_revlist(s.size())){} RollingHash(const string &s, ll b0): b1(b0), hs(hash(s)), rev(make_revlist(s.size())){} // hash(s[l, r)) inline 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 } vector 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; } private: static constexpr ll MASK31 = (1LL << 31)-1; static constexpr ll MASK30 = (1LL << 30)-1; static constexpr ll MASK61 = (1LL << 61)-1; static constexpr int bmin = 300; // a*b mod 2^61-1 inline ll Mul(const ll a, const ll b){ 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; return calcMod(au*bu*2 + midu + (midd << 31) + ad*bd); } // x mod 2^61-1 inline ll calcMod(ll x){ ll xu = x >> 61; ll xd = x & MASK61; ll res = xu+xd; if(res >= MOD) res -= MOD; return res; } // 逆元の前計算 vector make_revlist(int n){ vector rev(n); ll bm = 1; for(int i = 0; i < n; i++){ rev[i] = mpow(bm, MOD-2); bm = Mul(bm, b1); } return rev; } inline ll rnd(){ mt19937_64 mt{1ULL * chrono::steady_clock::now().time_since_epoch().count()}; return mt()%(MOD-bmin)+bmin; } inline ll mpow(ll a, ll x){ ll res = 1; for(; x > 0; x >>= 1){ if(x & 1){ res = Mul(res, a); } a = Mul(a, a); } return res; } }; int main(){ string s; cin >> s; int m; cin >> m; vector c(m); for(auto &it: c) cin >> it; RollingHash hs(s); ll ans = 0; for(int i = 0; i < m; i++){ auto hc = hs.hash(c[i]); for(int j = 0; j+c[i].size() <= s.size(); j++){ if(hs.get(j, j+c[i].size()) == hc[c[i].size()]){ ans++; } } } cout << ans << endl; return 0; }