#include #include #include #include #include #include #include #include template inline bool chmin(T &lhs, const U &rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template inline bool chmax(T &lhs, const U &rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } // [l, r) from l to r struct range { struct itr { int i; constexpr itr(int i_): i(i_) { } constexpr void operator ++ () { ++i; } constexpr int operator * () const { return i; } constexpr bool operator != (itr x) const { return i != x.i; } }; const itr l, r; constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { } constexpr itr begin() const { return l; } constexpr itr end() const { return r; } }; // [l, r) from r to l struct revrange { struct itr { int i; constexpr itr(int i_): i(i_) { } constexpr void operator ++ () { --i; } constexpr int operator * () const { return i; } constexpr bool operator != (itr x) const { return i != x.i; } }; const itr r, l; constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { } constexpr itr begin() const { return r; } constexpr itr end() const { return l; } }; template class hash_string { public: using mod_type = unsigned long long; using base_type = unsigned; using size_type = unsigned; static constexpr mod_type mod = (1ll << 61) - 1; static base_type base() { return T::value; } private: std::string M_string; std::vector M_power, M_hash; public: hash_string() { init(); } hash_string(const std::string &initial_) { init(initial_);} void init() { M_string = ""; M_power.assign(1, 1); M_hash.assign(1, 0); } void init(const std::string &initial_) { init(); add_string(initial_); } void add_string(const std::string &str) { size_type cur_size = M_string.size(); size_type next_size = M_string.size() + str.size(); M_string += str; M_power.resize(next_size + 1); M_hash.resize(next_size + 1); for (size_type i = cur_size; i < next_size; ++i) { M_power[i + 1] = (__uint128_t) M_power[i] * base() % mod; M_hash[i + 1] = ((__uint128_t) M_hash[i] * base() + M_string[i])% mod; } } mod_type hash(size_type l, size_type r) const { return (M_hash[r] + mod - ((__uint128_t) M_power[r - l] * M_hash[l]) % mod) % mod; } const std::string &get() const { return M_string; } }; struct rolling_hash_base { static inline const unsigned value = std::clock() ^ std::time(nullptr); }; using rolling_hash = hash_string; int main() { std::string S; int M; std::cin >> S >> M; std::unordered_map map; for (int i: range(0, M)) { std::string C; std::cin >> C; map[rolling_hash(C).hash(0, C.size())]++; } int ans = 0; rolling_hash hash(S); for (int len: range(1, std::min(S.size(), 10) + 1)) { for (int i: range(0, S.size() - len + 1)) { ans += map[hash.hash(i, i + len)]; } } std::cout << ans << '\n'; return 0; }