#include #include #include #include class RandomNumberGenerator { public: RandomNumberGenerator() : seed(std::chrono::steady_clock::now().time_since_epoch().count()) , mt(seed) {} unsigned long long operator()() { return mt(); } // Generate a random integer in a range [lo, hi). unsigned long long operator()( unsigned long long lo, unsigned long long hi = -1) { if (hi == -1) { hi = lo; lo = 0; } std::uniform_int_distribution dist(lo, hi - 1); return dist(mt); } void set_seed(int s) { seed = s; mt = decltype(mt)(seed); } long long get_seed() const { return seed; } private: long long seed; std::mt19937_64 mt; }; class RollingHash { public: RollingHash(const std::string &s, unsigned long long base = -1) : base(base != -1 ? base : rng(1ULL << 12, mod)) , base_p(s.size() + 1) , chash(s.size() + 1) { build(s); } // Hash a substring corresponding to a range [left, right). unsigned long long hash(int left, int right) { unsigned long long ret = chash[right] + mod - multiply(chash[left], base_p[right - left]); if (ret >= mod) ret -= mod; return ret; } unsigned long long get_base() { return base; } private: static constexpr unsigned long long mod = (1ULL << 61) - 1; RandomNumberGenerator rng; const unsigned long long base; std::vector base_p; std::vector chash; unsigned long long multiply(unsigned long long a, unsigned long long b) { static constexpr unsigned long long M30 = (1ULL << 30) - 1; static constexpr unsigned long long M31 = (1ULL << 31) - 1; unsigned long long au = a >> 31, ad = a & M31, bu = b >> 31, bd = b & M31, m = ad * bu + au * bd, mu = m >> 30, md = m & M30; return (2 * au * bu + mu + (md << 31) + ad * bd) % mod; } void build(const std::string &s) { int n = s.size(); base_p[0] = 1; for (int i = 0; i < n; i++) { chash[i + 1] = (multiply(chash[i], base) + s[i]) % mod; base_p[i + 1] = multiply(base_p[i], base); } } }; class DoubleRollingHash { public: DoubleRollingHash(const std::string &s, unsigned long long basel = -1, unsigned long long baser = -1) : hashl(s, basel), hashr(s, baser) {} std::pair hash(int left, int right) { return { hashl.hash(left, right), hashr.hash(left, right) }; } std::pair get_base() { return { hashl.get_base(), hashr.get_base() }; } private: RollingHash hashl, hashr; }; int main() { std::string s; std::cin >> s; int n = s.size(); int m; std::cin >> m; std::vector t(m); for (int i = 0; i < m; i++) std::cin >> t[i]; RollingHash rh(s); auto base = rh.get_base(); int ans = 0; for (int i = 0; i < m; i++) { auto hash = RollingHash( t[i], base).hash(0, t[i].size()); for (int j = 0; j + t[i].size() <= n; j++) { ans += hash == rh.hash(j, j + t[i].size()); } } std::cout << ans << std::endl; return 0; }