/* 文字列 S の RollingHash を扱う構造体 hash(s[0, i)) := s_0*b^0 + s_1*b^1 + ... + s_(i-1)*b^(i-1) b は基数 [2, MOD) から乱択 32bit の mod 2つver RollingHash hs(s) 文字列 s の RollingHashを構築 基数 b1, b2 は乱択 RollingHash hs(s, b1, b2) 文字列 s の RollingHashを構築 基数 b1, b2 はこちらで指定 get(l, r) s[l, r) の hash を取得 */ #include #include #include #include #include #include using namespace std; using ll = long long; struct RollingHash{ static constexpr ll MOD1 = 998244353; static constexpr ll MOD2 = 1000000007; const ll b1, b2; vector hs1, hs2; vector rev1, rev2; RollingHash(const string &s): b1(rnd()), b2(rnd()){ init(s); } RollingHash(const string &s, ll b1, ll b2): b1(b1), b2(b2){ init(s); } // hash1(s[l, r)), hash2(s[l, r)) pair get(int l, int r){ return { (hs1[r]-hs1[l]+MOD1)%MOD1*rev1[l]%MOD1, (hs2[r]-hs2[l]+MOD2)%MOD2*rev2[l]%MOD2 }; } private: void init(const string &s){ hs1 = vector(s.size()+1); rev1 = vector(s.size()); ll bm1 = 1; for(int i = 0; i < s.size(); i++){ hs1[i+1] = (hs1[i]+bm1*(s[i]-'A'+1))%MOD1; rev1[i] = mpow1(bm1, MOD1-2); bm1 *= b1; bm1 %= MOD1; } hs2 = vector(s.size()+1); rev2 = vector(s.size()); ll bm2 = b2; for(int i = 0; i < s.size(); i++){ hs2[i+1] = (hs2[i]+bm2*(s[i]-'A'+1))%MOD2; rev2[i] = mpow2(bm2, MOD2-2); bm2 *= b2; bm2 %= MOD2; } } ll rnd(){ mt19937 mt{chrono::steady_clock::now().time_since_epoch().count()}; return mt()%(MOD1-2)+2; } ll mpow1(ll a, ll x){ ll res = 1; for(; x > 0; x >>= 1){ if(x & 1){ res *= a; res %= MOD1; } a *= a; a %= MOD1; } return res; } ll mpow2(ll a, ll x){ ll res = 1; for(; x > 0; x >>= 1){ if(x & 1){ res *= a; res %= MOD2; } a *= a; a %= MOD2; } return res; } }; // https://yukicoder.me/problems/no/430 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, hs.b2); ll ans = 0; for(int i = 0; i < m; i++){ 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 << i << " " << j << endl; ans++; } } } cout << ans << endl; return 0; }