#line 1 "test/yuki/No430.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/430" #include #line 2 "src/data-structure/hash_map.hpp" #include #include namespace kyopro { 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; u32 get_hash(const Key& k) const { return ((u64)k * r) >> shift; } static constexpr int mod_msk = (1 << 6) - 1; public: explicit 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 /** * @brief Hash Map */ #line 2 "src/stream.hpp" #include #include #include #line 3 "src/internal/type_traits.hpp" #include #include #include #include namespace kyopro { namespace internal { 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 * = nullptr> struct int_least { using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if>; }; template * = nullptr> struct uint_least { 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>; struct modint_base {}; template using is_modint = std::is_base_of; template using is_modint_t = std::enable_if_t::value>; // is_integral template using is_integral_t = std::enable_if_t || std::is_same_v || std::is_same_v>; }; // namespace internal }; // namespace kyopro /* * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8 */ #line 6 "src/stream.hpp" namespace kyopro { inline void single_read(char& c) { c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); } template * = nullptr> inline void single_read(T& a) { a = 0; bool is_negative = false; char c = getchar_unlocked(); while (isspace(c)) { c = getchar_unlocked(); } if (c == '-') is_negative = true, c = getchar_unlocked(); while (isdigit(c)) { a = 10 * a + (c - '0'); c = getchar_unlocked(); } if (is_negative) a *= -1; } template * = nullptr> inline void single_read(T& a) { long long x; single_read(x); a = T(x); } inline void single_read(std::string& str) noexcept { char c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); while (!isspace(c)) { str += c; c = getchar_unlocked(); } } template inline void read(T& x) noexcept {single_read(x);} template inline void read(Head& head, Tail&... tail) noexcept { single_read(head), read(tail...); } inline void single_write(char c) noexcept { putchar_unlocked(c); } template * = nullptr> inline void single_write(T a) noexcept { if (!a) { putchar_unlocked('0'); return; } if constexpr (std::is_signed_v) { if (a < 0) putchar_unlocked('-'), a *= -1; } constexpr int d = std::numeric_limits::digits10; char s[d + 1]; int now = d + 1; while (a) { s[--now] = (char)'0' + a % 10; a /= 10; } while (now <= d) putchar_unlocked(s[now++]); } template * = nullptr> inline void single_write(T a) noexcept { single_write(a.val()); } inline void single_write(const std::string& str) noexcept { for (auto c : str) { putchar_unlocked(c); } } template inline void write(T x) noexcept { single_write(x); } template inline void write(Head head, Tail... tail) noexcept { single_write(head); putchar_unlocked(' '); write(tail...); } template inline void put(Args... x) noexcept { write(x...); putchar_unlocked('\n'); } }; // namespace kyopro /** * @brief 高速入出力 */ #line 3 "src/string/rolling_hash.hpp" #include #line 5 "src/string/rolling_hash.hpp" #include #line 2 "src/math/gcd.hpp" #include #include namespace kyopro { template constexpr inline T _gcd(T a, T b) noexcept { 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 || !b) { return a + b; } if (a >= b) { a -= b; a >>= __builtin_ctzll(a); } else { b -= a; b >>= __builtin_ctzll(b); } } return a << d; } template constexpr inline T ext_gcd(T a, T b, T& x, T& y) noexcept { 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 3 "src/math/mod_pow.hpp" namespace kyopro { /** * @brief バイナリ法 */ 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 u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; // mod static constexpr u64 msk30 = (static_cast(1) << 30) - 1; static constexpr u64 msk61 = (static_cast(1) << 31) - 1; const std::string str; std::vector _hash, _pow; static constexpr u64 mod = (static_cast(1) << 61) - 1; static constexpr u64 primitive_root = 37; static constexpr uint mapping_max = (uint)'Z' + 2; static u64 base; private: constexpr u64 mul(u64 a, u64 b) const { u128 t = (u128)a * b; t = (t >> 61) + (t & mod); if (t >= mod) { t -= mod; } return t; } constexpr u64 mapping(char c) const { return (u64)c; } static u64 generate() { static std::mt19937_64 engine( std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution rand(1, mod - 1); return rand(engine); } static void generate_base() { if (base != 0) { return; } u64 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; } } } u64 hash(int l, int r) const { assert(0 <= l && l <= r && r <= str.size()); u64 res = mod + _hash[r] - mul(_hash[l], _pow[r - l]); return res < mod ? res : res - mod; } u64 get_all() const { return _hash.back(); } int size() const { return str.size(); } static int lcp(const RollingHash& a, const RollingHash& b, int start_a, int start_b) { int ok = 0; int ng = std::min(a.size() - start_a, b.size() - start_b) + 1; while (ng - ok > 1) { int md = (ok + ng) >> 1; if (a.hash(start_a, start_a + md) == b.hash(start_b, start_b + md)) { ok = md; } else { ng = md; } } return ok; } }; } // namespace kyopro typename kyopro::RollingHash::u64 kyopro::RollingHash::base; /** * @brief Rolling Hash */ #line 6 "test/yuki/No430.test.cpp" using namespace std; using namespace kyopro; int main() { string s; int m; read(s, m); RollingHash S(s); 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.hash(i, j)]; } } long long ans = 0; for (int i = 0; i < m; ++i) { string c; read(c); ans += hash_count[kyopro::RollingHash(c).get_all()]; } put(ans); }