#include using namespace std; /** * @brief RollingHash */ struct RollingHash { private: static const uint64_t mod = (1ull << 61ull) - 1; using uint128_t = __uint128_t; std::vector power; const uint64_t base; static inline uint64_t add(uint64_t a, uint64_t b) { if((a += b) >= mod) a -= mod; return a; } static inline uint64_t mul(uint64_t a, uint64_t b) { uint128_t c = (uint128_t)a * b; return add(c >> 61, c & mod); } static inline uint64_t generate_base() { std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution< uint64_t > rand(1, RollingHash::mod - 1); return rand(mt); } 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); } } } public: RollingHash(uint64_t base = generate_base()) : base(base), power{1} {} std::vector build(const std::string &s) const { int sz = s.size(); std::vector hashed(sz + 1); for(int i = 0; i < sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } template std::vector build(const std::vector &s) const { int sz = s.size(); std::vector hashed(sz + 1); for(int i = 0; i < sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } uint64_t hash(const std::vector &s, int l, int r) { expand(r - l); return add(s[r], mod - mul(s[l], power[r - l])); } uint64_t all_hash(const std::vector &s) { return s.back(); } }; int main() { RollingHash rh; string S; int M; cin >> S >> M; auto hash = rh.build(S); unordered_map cnt; for(int i = 0; i < S.size(); ++i) { for(int j = 0; j < 10; ++j) { if(i + j < S.size()) cnt[rh.hash(hash, i, i + j + 1)]++; } } string T; int ans = 0; for(int i = 0; i < M; ++i) { cin >> T; ans += cnt[rh.all_hash(rh.build(T))]; } cout << ans << endl; }