#include using namespace std; class RollingHash { private: template static T random(T lo, T hi) { static std::mt19937 mt{std::random_device()()}; std::uniform_int_distribution uid(lo, hi - 1); return uid(mt); } constexpr static std::uint64_t mod = (UINT64_C(1) << 61) - 1; static inline std::uint64_t base = random(UINT64_C(10007), UINT64_C(1) << 28); std::vector powers; std::vector hashes; std::uint64_t add(std::uint64_t a, const std::uint64_t b) const { if ((a += b) >= mod) a -= mod; return a; } std::uint64_t sub(std::uint64_t a, const std::uint64_t b) const { if (a < b) a += mod; a -= b; return a; } std::uint64_t mul(const std::uint64_t a, const std::uint64_t b) const { std::uint64_t ah = a >> 31, al = a & ((UINT64_C(1) << 31) - 1); std::uint64_t bh = b >> 31, bl = b & ((UINT64_C(1) << 31) - 1), m = ah * bl + al * bh; std::uint64_t v = (2 * ah * bh) + (m >> 30) + ((m & ((UINT64_C(1) << 30) - 1)) << 31) + al * bl; return (v & ((UINT64_C(1) << 61) - 1)) + (v >> 61); } public: template explicit RollingHash(const T &v) : powers(v.size() + 1, 1), hashes(v.size() + 1, 0) { for (std::size_t i = 0; i < v.size(); i++) { powers[i + 1] = mul(powers[i], base); hashes[i + 1] = add(mul(hashes[i], base), v[i]); } } std::uint64_t query(const std::size_t l, const std::size_t r) const { return sub(hashes[r], mul(hashes[l], powers[r - l])); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string S; cin >> S; RollingHash rhs(S); int M; cin >> M; int res = 0; for (int i = 0; i < M; i++) { string T; cin >> T; RollingHash rht(T); for (int j = 0; j + (int)T.size() < (int)S.size() + 1; j++) { if (rhs.query(j, j + (int)T.size()) == rht.query(0, (int)T.size())) res++; } } cout << res << '\n'; return 0; }