#define PROBLEM "https://yukicoder.me/problems/no/430" #include #include #include #include #include #include #include #include namespace hash_impl { static constexpr unsigned long long mod = (1ULL << 61) - 1; struct modint { modint() : _v(0) {} modint(unsigned long long v) { v = (v >> 61) + (v & mod); if (v >= mod) v -= mod; _v = v; } unsigned long long val() const { return _v; } modint& operator+=(const modint& rhs) { _v += rhs._v; if (_v >= mod) _v -= mod; return *this; } modint& operator-=(const modint& rhs) { if (_v < rhs._v) _v += mod; _v -= rhs._v; return *this; } modint& operator*=(const modint& rhs) { __uint128_t t = __uint128_t(_v) * rhs._v; t = (t >> 61) + (t & mod); if (t >= mod) t -= mod; _v = t; return *this; } modint& operator/=(const modint& rhs) { return *this = *this * rhs.inv(); } modint operator-() const { return modint() - *this; } modint pow(long long n) const { assert(0 <= n); modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } modint inv() const { return pow(mod - 2); } friend modint operator+(const modint& lhs, const modint& rhs) { return modint(lhs) += rhs; } friend modint operator-(const modint& lhs, const modint& rhs) { return modint(lhs) -= rhs; } friend modint operator*(const modint& lhs, const modint& rhs) { return modint(lhs) *= rhs; } friend bool operator==(const modint& lhs, const modint& rhs) { return lhs._v == rhs._v; } friend bool operator!=(const modint& lhs, const modint& rhs) { return lhs._v != rhs._v; } friend std::ostream& operator<<(std::ostream& os, const modint& rhs) { os << rhs._v; } private: unsigned long long _v; }; uint64_t generate_base() { std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution rand(2, mod - 1); return rand(mt); } modint base(generate_base()); std::vector power{1}; modint get_pow(int n) { if (n < int(power.size())) return power[n]; int m = power.size(); power.resize(n + 1); for (int i = m; i <= n; i++) power[i] = power[i - 1] * base; return power[n]; } }; // namespace hash_impl struct Hash { using mint = hash_impl::modint; mint x; int len; Hash() : x(0), len(0) {} Hash(mint x, int len) : x(x), len(len) {} Hash& operator+=(const Hash& rhs) { x = x * hash_impl::get_pow(rhs.len) + rhs.x; len += rhs.len; return *this; } Hash operator+(const Hash& rhs) { return *this += rhs; } bool operator==(const Hash& rhs) { return x == rhs.x and len == rhs.len; } }; struct ReversibleHash { using mint = hash_impl::modint; mint x, rx; int len; ReversibleHash() : x(0), rx(0), len(0) {} ReversibleHash(mint x) : x(x), rx(x), len(1) {} ReversibleHash(mint x, mint rx, int len) : x(x), rx(rx), len(len) {} ReversibleHash rev() const { return ReversibleHash(rx, x, len); } ReversibleHash operator+=(const ReversibleHash& rhs) { x = x * hash_impl::get_pow(rhs.len) + rhs.x; rx = rx + rhs.rx * hash_impl::get_pow(len); len += rhs.len; return *this; } ReversibleHash operator+(const ReversibleHash& rhs) { return *this += rhs; } bool operator==(const ReversibleHash& rhs) { return x == rhs.x and rx == rhs.rx and len == rhs.len; } }; struct RollingHash { using mint = hash_impl::modint; RollingHash() : power{mint(1)} {} template std::vector build(const T& s) const { int n = s.size(); std::vector hash(n + 1); hash[0] = 0; for (int i = 0; i < n; i++) hash[i + 1] = hash[i] * base + s[i]; return hash; } template mint get(const T& s) const { mint res = 0; for (const auto& x : s) res = res * base + x; return res; } mint query(const std::vector& hash, int l, int r) { assert(0 <= l && l <= r); extend(r - l); return hash[r] - hash[l] * power[r - l]; } mint combine(mint h1, mint h2, int h2_len) { extend(h2_len); return h1 * power[h2_len] + h2; } int lcp(const std::vector& a, int l1, int r1, const std::vector& b, int l2, int r2) { int len = std::min(r1 - l1, r2 - l2); int lb = 0, ub = len + 1; while (ub - lb > 1) { int mid = (lb + ub) >> 1; (query(a, l1, l1 + mid) == query(b, l2, l2 + mid) ? lb : ub) = mid; } return lb; } private: static constexpr unsigned long long mod = hash_impl::mod; const mint base = hash_impl::base; std::vector power; inline void extend(size_t len) { if (power.size() > len) return; int pre = power.size(); power.resize(len + 1); for (int i = pre - 1; i < len; i++) power[i + 1] = power[i] * base; } }; int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); std::string S; std::cin >> S; RollingHash RH; auto v = RH.build(S); std::map mp; for (size_t j = 1; j <= 10; j++) { for (size_t i = 0; i + j <= S.size(); i++) { mp[RH.query(v, i, i + j).val()]++; } } int M, ans = 0; std::cin >> M; for (; M--;) { std::string C; std::cin >> C; ans += mp[RH.get(C).val()]; } std::cout << ans << '\n'; }