// >>> TEMPLATES #include using namespace std; using ll = long long; using ld = long double; using i32 = int32_t; using i64 = int64_t; #define int ll #define double ld #define rep(i,n) for (int i = 0; i < (int)(n); i++) #define rep1(i,n) for (int i = 1; i <= (int)(n); i++) #define repR(i,n) for (int i = (int)(n)-1; i >= 0; i--) #define rep1R(i,n) for (int i = (int)(n); i >= 1; i--) #define loop(i,a,B) for (int i = a; i B; i++) #define loopR(i,a,B) for (int i = a; i B; i--) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define pb push_back #define eb emplace_back #define mp make_pair #define fst first #define snd second auto constexpr INF32 = numeric_limits::max()/2-1; auto constexpr INF64 = numeric_limits::max()/2-1; auto constexpr INF = numeric_limits::max()/2-1; #ifdef LOCAL #include "debug.hpp" #define dump(...) cerr << "[" << setw(3) << __LINE__ << ":" << __FUNCTION__ << "] ", dump_impl(#__VA_ARGS__, __VA_ARGS__) #define say(x) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] " << x << endl #define debug if (1) #else #define dump(...) (void)(0) #define say(x) (void)(0) #define debug if (0) #endif template using pque_max = priority_queue; template using pque_min = priority_queue, greater >; template ::value>::type> ostream& operator<<(ostream& os, T const& v) { bool f = true; for (auto const& x : v) os << (f ? "" : " ") << x, f = false; return os; } template ::value>::type> istream& operator>>(istream& is, T &v) { for (auto& x : v) is >> x; return is; } template istream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } iosetup; template struct FixPoint : private F { constexpr FixPoint(F&& f) : F(forward(f)) {} template constexpr auto operator()(T&&... x) const { return F::operator()(*this, forward(x)...); } }; struct MakeFixPoint { template constexpr auto operator|(F&& f) const { return FixPoint(forward(f)); } }; #define MFP MakeFixPoint()| #define def(name, ...) auto name = MFP [&](auto &&name, __VA_ARGS__) template struct vec_impl { using type = vector::type>; template static type make_v(size_t n, U&&... x) { return type(n, vec_impl::make_v(forward(x)...)); } }; template struct vec_impl { using type = T; static type make_v(T const& x = {}) { return x; } }; template using vec = typename vec_impl::type; template auto make_v(Args&&... args) { return vec_impl::make_v(forward(args)...); } template void quit(T const& x) { cout << x << endl; exit(0); } template constexpr bool chmin(T& x, T const& y) { if (x > y) { x = y; return true; } return false; } template constexpr bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; } template constexpr auto sumof(It b, It e) { return accumulate(b,e,typename iterator_traits::value_type{}); } template int sz(T const& x) { return x.size(); } template int lbd(C const& v, T const& x) { return lower_bound(v.begin(), v.end(), x)-v.begin(); } template int ubd(C const& v, T const& x) { return upper_bound(v.begin(), v.end(), x)-v.begin(); } template int ppt(C const& v, F f) { return partition_point(v.begin(), v.end(), f)-v.begin(); } // <<< // >>> rolling hash template struct RollingHash { using u64 = uint64_t; using u32 = uint32_t; static constexpr u64 mod = (1ull<<61) - 1; static u64 base; static void init_base() { if (base) return; mt19937_64 mt(random_device{}()); base = uniform_int_distribution(300,mod-300)(mt); } static constexpr u64 mul(u64 a, u64 b) { constexpr u64 mask30 = (1ull << 30) - 1; constexpr u64 mask31 = (1ull << 31) - 1; u64 au = a >> 31; u64 ad = a & mask31; u64 bu = b >> 31; u64 bd = b & mask31; u64 mid = ad * bu + au * bd; u64 midu = mid >> 30; u64 midd = mid & mask30; u64 val = au * bu * 2 + midu + (midd << 31) + ad * bd; return (val & mod) + (val >> 61); } static constexpr u64 take_mod(u64 val) { val = (val & mod) + (val >> 61); if (val >= mod) val -= mod; return val; } static constexpr u32 xorshift(u32 x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } Str s; vector hash; static vector pow; RollingHash(Str const& s = "") : s(s) { init_base(); hash.resize(s.size()+1); rep (i,s.size()) { hash[i+1] = take_mod(mul(hash[i],base) + (xorshift(s[i]^u32(base)))); } if (pow.size() < s.size()+1) { auto m = max(signed(pow.size())-1, 0); pow.resize(s.size()+1,1); for (int i = m; i+1 < (int)pow.size(); ++i) { pow[i+1] = take_mod(mul(pow[i],base)); } } } u64 get() const { return hash.back(); } u64 get(int l, int r) const { return take_mod(3*mod - mul(hash[l],pow[r-l]) + hash[r]); } }; template uint64_t RollingHash::base; template vector RollingHash::pow; using ull = uint64_t; // <<< int32_t main() { string s,t; cin >> s >> t; int n = s.size(), m = t.size(); RollingHash s_rh(s), t_rh(t); int cnt = 0; for (int i = 0; i+m <= n; ) { if (s_rh.get(i,i+m) == t_rh.get()) { cnt++; i += m-1; } else { i++; } } cout << cnt << endl; }