#include #line 1 "test/yuki/No430.test.cpp" #define PROBLEM "https://yukicoder.me/submissions/865256" #line 2 "src/data-structure/hash_map.hpp" #include #include namespace kyopro { /// @brief HashMap template class hash_map { using u32 = uint32_t; using u64 = uint64_t; u64* flag = new u64[n]; Key* keys = new Key[n]; Val* vals = new Val[n]; static constexpr u32 shift = 64 - std::__lg(n); u64 r; inline u32 get_hash(const Key& k) const { return ((u64)k * r) >> shift; } static constexpr uint8_t mod_msk = (1 << 6) - 1; public: explicit constexpr hash_map() { r = std::chrono::steady_clock::now().time_since_epoch().count(); r ^= r >> 16; r ^= r << 32; } Val& operator[](const Key& k) { u32 hash = get_hash(k); while (1) { if (!(flag[hash >> 6] & (static_cast(1) << (hash & mod_msk)))) { keys[hash] = k; flag[hash >> 6] |= static_cast(1) << (hash & mod_msk); return vals[hash] = default_val; } if (keys[hash] == k) return vals[hash]; hash = (hash + 1) & (n - 1); } } Val* find(const Key& k) const { u32 hash = get_hash(k); while (1) { if (!(flag[hash >> 6] & (static_cast(1) << (hash & mod_msk)))) return nullptr; if (keys[hash] == k) return &(vals[hash]); hash = (hash + 1) & (n - 1); } } }; }; // namespace kyopro #line 3 "src/string/rolling_hash.hpp" #include #include #include #line 2 "src/math/gcd.hpp" #include #include namespace kyopro { template constexpr T _gcd(T a, T b) { assert(a >= 0 && b >= 0); if (a == 0 || b == 0) return a + b; int d = std::min(__builtin_ctzll(a), __builtin_ctzll(b)); a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b); while (a != b) { if (a == 0 || b == 0) { return a + b; } if (a > b) { a -= b; a >>= __builtin_ctzll(a); } else { b -= a; b >>= __builtin_ctzll(b); } } return a << d; } template constexpr T ext_gcd(T a, T b, T& x, T& y) { x = 1, y = 0; T nx = 0, ny = 1; while (b) { T q = a / b; std::tie(a, b) = std::pair{b, a % b}; std::tie(x, nx) = std::pair{nx, x - nx * q}; std::tie(y, ny) = std::pair{ny, y - ny * q}; } return a; } }; // namespace kyopro #line 2 "src/internal/type_traits.hpp" #include #include #include #include namespace kyopro { namespace internal { /// @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8 template struct first_enabled {}; template struct first_enabled, Args...> { using type = T; }; template struct first_enabled, Args...> : first_enabled {}; template struct first_enabled { using type = T; }; template using first_enabled_t = typename first_enabled::type; template struct int_least { static_assert(dgt <= 128, "digit have to be less or equals to 128"); using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if >; }; template struct uint_least { static_assert(dgt <= 128, "digit have to be less or equals to 128"); using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if >; }; template using int_least_t = typename int_least::type; template using uint_least_t = typename uint_least::type; template using double_size_uint_t = uint_least_t<2 * std::numeric_limits::digits>; template using double_size_int_t = int_least_t<2 * std::numeric_limits::digits>; }; // namespace internal }; // namespace kyopro #line 3 "src/math/mod_pow.hpp" namespace kyopro { ///@brief mod pow(繰り返しニ乗法) template constexpr T mod_pow(internal::double_size_uint_t base, T exp, T mod) { internal::double_size_uint_t ans = (mod == 1 ? 0 : 1); base %= mod; while (exp) { if (exp & 1) { ans *= base; ans %= mod; } base *= base; base %= mod; exp >>= 1; } return ans; } }; // namespace kyopro #line 8 "src/string/rolling_hash.hpp" namespace kyopro { class RollingHash { using ull = uint_fast64_t; using i128 = __int128_t; using u128 = __uint128_t; // mod static constexpr ull msk30 = (1ul << 30) - 1; static constexpr ull msk61 = (1ul << 31) - 1; const std::string str; std::vector hash, pow; static constexpr ull mod = (1uL << 61) - 1; static constexpr ull primitive_root = 37; public: static const uint mapping_max = (uint)'Z' + 2; static ull base; private: constexpr ull mul(const u128& a, const u128& b) const { u128 t = a * b; t = (t >> 61) + (t & mod); if (t >= mod) { t -= mod; } return t; } constexpr ull mapping(const char& c) const { return (ull)c; // 変更する? } static inline ull generate() { std::mt19937_64 engine( std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution rand(1uL, mod - 1); return rand(engine); } static inline void generate_base() { if (base != 0) { return; } ull r = mod - 1; while (_gcd(r, mod - 1) != 1 || r <= mapping_max) { r = generate(); } base = mod_pow(primitive_root, r, mod); } public: RollingHash() : str() {} RollingHash(const std::string& str) : str(str) { generate_base(); build(); } void build() { hash.resize(str.size() + 1); pow.resize(str.size() + 1, 1); for (int i = 0; i < (int)str.size(); i++) { hash[i + 1] = mul(hash[i], base) + mapping(str[i]); pow[i + 1] = mul(pow[i], base); if (hash[i + 1] >= mod) { hash[i + 1] -= mod; } } } ull range(int l, int r) const { assert(0 <= l && l <= r && r <= str.size()); ull res = mod + hash[r] - mul(hash[l], pow[r - l]); return res < mod ? res : res - mod; } ull get_all() const { return hash.back(); } int size() const { return str.size(); } static int lcp(const RollingHash& a, const RollingHash& b, const int& start_a, const int& start_b) { int ok = 0; int ng = std::min(a.size() - start_a, b.size() - start_b) + 1; while (abs(ok - ng) > 1) { int md = (ok + ng) >> 1; if (a.range(start_a, start_a + md) == b.range(start_b, start_b + md)) { ok = md; } else { ng = md; } } return ok; } }; } // namespace kyopro typename kyopro::RollingHash::ull kyopro::RollingHash::base; ///@brief Rollinghash(ローリングハッシュ) #line 5 "test/yuki/No430.test.cpp" int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::string s; int m; std::cin >> s >> m; kyopro::RollingHash S(s); kyopro::hash_map hash_count; for (int i = 0; i < (int)s.size(); ++i) { for (int length = 1; length <= 10 && i + length <= (int)s.size(); ++length) { int j = i + length; ++hash_count[S.range(i, j)]; } } long long ans = 0; for (int i = 0; i < m; ++i) { std::string c; std::cin >> c; ans += hash_count[kyopro::RollingHash(c).get_all()]; } std::cout << ans << '\n'; }