#pragma region KCLC // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; #include #include using Bint = boost::multiprecision::cpp_int; using Real = boost::multiprecision::number>; using ll = long long; using ld = long double; using pii = pair; using pll = pair; #define pb push_back #define mp make_pair #define mt make_tuple #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define elif else if #define updiv(N, X) ((N + X - 1) / X) #define sigma(a, b) ((a + b) * (b - a + 1) / 2) #ifdef LOCAL #include "debug.hpp" #else #define debug(...) #endif struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }; } fast_ios_; template inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); } template struct Fp { long long val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() const { return MOD; } constexpr Fp operator-() const noexcept { return val ? MOD - val : 0; } constexpr Fp operator+(const Fp& r) const noexcept { return Fp(*this) += r; } constexpr Fp operator-(const Fp& r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator*(const Fp& r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator/(const Fp& r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator+=(const Fp& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator-=(const Fp& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator*=(const Fp& r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator/=(const Fp& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator==(const Fp& r) const noexcept { return this->val == r.val; } constexpr bool operator!=(const Fp& r) const noexcept { return this->val != r.val; } friend constexpr istream& operator>>(istream& is, Fp& x) noexcept { is >> x.val; x.val %= MOD; if (x.val < 0) x.val += MOD; return is; } friend constexpr ostream& operator<<(ostream& os, const Fp& x) noexcept { return os << x.val; } friend constexpr Fp modpow(const Fp& r, long long n) noexcept { if (n == 0) return 1; if (n < 0) return modpow(modinv(r), -n); auto t = modpow(r, n / 2); t = t * t; if (n & 1) t = t * r; return t; } friend constexpr Fp modinv(const Fp& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } return Fp(u); } }; template struct BiCoef { vector fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) noexcept { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int modular = fact_[0].getmod(); for (int i = 2; i < n; i++) { fact_[i] = fact_[i - 1] * i; inv_[i] = -inv_[modular % i] * (modular / i); finv_[i] = finv_[i - 1] * inv_[i]; } } constexpr T com(int n, int k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n - k]; } constexpr T hom(int n, int k) const noexcept { n += k - 1; if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n - k]; } constexpr T fact(int n) const noexcept { if (n < 0) return 0; return fact_[n]; } constexpr T inv(int n) const noexcept { if (n < 0) return 0; return inv_[n]; } constexpr T finv(int n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; long long mypow(long long a, long long n) { long long res = 1; while (n > 0) { if (n & 1) res = res * a; a = a * a; n >>= 1; } return res; } long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } long double dis(pair a, pair b) { return sqrt(pow((ld)a.first - b.first, 2) + pow((ld)a.second - b.second, 2)); } long long nCk(int n, int k) { long long res = 1; for (int i = 1; i <= k; i++) { res *= (n - k + i) / i; } return res; } #pragma endregion KCLC //---------------------------------------------------------------------------- constexpr int inf = 1 << 30; constexpr ll INF = 1LL << 60; constexpr int dx[] = {1, 0, -1, 0, 1, -1, 1, -1}; constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; constexpr int mod = 998244353; constexpr int MOD = 1e9 + 7; using mint = Fp; BiCoef bc; struct RollingHash { static const uint64_t mod = (1ull << 61ull) - 1; vector power, hash; const uint64_t base; // [1, mod)のランダムなbaseを生成 static inline uint64_t generate_base() { mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution rand((uint64_t)1, (uint64_t)mod - 1); return rand(engine); } // 加算 static inline uint64_t add(uint64_t a, uint64_t b) { if ((a += b) >= mod) a -= mod; return a; } // 乗算 (__uint128_tを使用) static inline uint64_t mul(uint64_t a, uint64_t b) { __uint128_t c = (__uint128_t)a * b; return add(c >> 61, c & mod); } inline void expand(size_t sz) { if (power.size() < sz + 1) { int pre_sz = (int)power.size(); power.resize(sz + 1); for (int i = pre_sz - 1; i < sz; i++) { power[i + 1] = mul(power[i], base); } } } explicit RollingHash(uint64_t base = generate_base()) : base(base), power{1} {} // 文字列Sのハッシュを返す vector build(string S) { vector hash(S.size() + 1); for (int i = 0; i < S.size(); i++) { hash[i + 1] = add(mul(hash[i], base), S[i]); } return hash; } // hashの[l,r)のハッシュ値を返す uint64_t get(vector& hash, int l, int r) { expand(r - l); return add(hash[r], mod - mul(hash[l], power[r - l])); } // ハッシュ値h1と長さh2lenのハッシュ値h2を結合 uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) { expand(h2len); return add(mul(h1, power[h2len]), h2); } //hash1の区間[l1,r1)とhash2の区間[l2,r2)のlcp(最長共通接頭辞)の長さを返す (二部探索を用いる) int getLCP(vector& hash1, int l1, int r1, vector& hash2, int l2, int r2) { int len = min(r1 - l1, r2 - l2); int ok = 0; int ng = len + 1; int mid; while (ng - ok > 1) { mid = (ok + ng) / 2; if (get(hash1, l1, l1 + mid) == get(hash2, l2, l2 + mid)) ok = mid; else ng = mid; } return ok; } }; int main() { string s; cin>>s; int ssiz=s.size(); RollingHash rh; auto shash=rh.build(s); int Q; cin>>Q; int ans=0; for(int i=0;i>t; int tsiz=t.size(); auto thash=rh.build(t); for(int j=0;j<=ssiz-tsiz;j++){ if(rh.get(shash,j,j+tsiz)==rh.get(thash,0,tsiz)){ ans++; } } } cout<