#921895 (C++23) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: AC2K
• 提出日時: 2023-10-23 06:41:35
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 23 ms / 2,000 ms
• コード長: 11,461 bytes
• コンパイル時間: 1,294 ms
• コンパイル使用メモリ: 132,500 KB
• 実行使用メモリ: 16,640 KB
• 最終ジャッジ日時: 2024-11-10 01:07:36
• 合計ジャッジ時間: 2,091 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	23 ms; 16,512 KB
testcase_02	AC	11 ms; 8,704 KB
testcase_03	AC	15 ms; 13,952 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	3 ms; 5,248 KB
testcase_08	AC	23 ms; 16,640 KB
testcase_09	AC	4 ms; 5,376 KB
testcase_10	AC	11 ms; 15,872 KB
testcase_11	AC	19 ms; 16,512 KB
testcase_12	AC	18 ms; 16,512 KB
testcase_13	AC	19 ms; 16,512 KB
testcase_14	AC	18 ms; 16,512 KB
testcase_15	AC	18 ms; 16,512 KB
testcase_16	AC	15 ms; 16,128 KB
testcase_17	AC	15 ms; 15,488 KB

ソースコード

#line 1 "test/yuki/No430.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/430"
#include <iostream>
#line 2 "src/data-structure/hash_map.hpp"
#include <bits/stl_algobase.h>
#include <chrono>
namespace kyopro {
template <typename Key,
          typename Val,
          uint32_t n = 1 << 20,
          Val default_val = Val()>
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<u64>(1) << (hash & mod_msk)))) {
                keys[hash] = k;
                flag[hash >> 6] |= static_cast<u64>(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<u64>(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 <ctype.h>
#include <stdio.h>
#include <string>
#line 3 "src/internal/type_traits.hpp"
#include <limits>
#include <numeric>
#include <typeinfo>
#include <cstdint>

namespace kyopro {
namespace internal {
template <typename... Args> struct first_enabled {};

template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
    using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
    : first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
    using type = T;
};

template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;

template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {
    using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,
                                 std::enable_if<dgt <= 16, std::int16_t>,
                                 std::enable_if<dgt <= 32, std::int32_t>,
                                 std::enable_if<dgt <= 64, std::int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t>>;
};

template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {
    using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,
                                 std::enable_if<dgt <= 16, std::uint16_t>,
                                 std::enable_if<dgt <= 32, std::uint32_t>,
                                 std::enable_if<dgt <= 64, std::uint64_t>,
                                 std::enable_if<dgt <= 128, __uint128_t>>;
};

template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;

template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;

template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;

struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;


// is_integral
template <typename T>
using is_integral_t =
    std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
                   std::is_same_v<T, __uint128_t>>;
};  // 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 <typename T, internal::is_integral_t<T>* = 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 <typename T, internal::is_modint_t<T>* = 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<typename T>
inline void read(T& x) noexcept {single_read(x);}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail&... tail) noexcept {
    single_read(head), read(tail...);
}

inline void single_write(char c) noexcept { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_write(T a) noexcept {
    if (!a) {
        putchar_unlocked('0');
        return;
    }
    if constexpr (std::is_signed_v<T>) {
        if (a < 0) putchar_unlocked('-'), a *= -1;
    }
    constexpr int d = std::numeric_limits<T>::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 <typename T, internal::is_modint_t<T>* = 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 <typename T> inline void write(T x) noexcept { single_write(x); }
template <typename Head, typename... Tail>
inline void write(Head head, Tail... tail) noexcept {
    single_write(head);
    putchar_unlocked(' ');
    write(tail...);
}
template <typename... Args> inline void put(Args... x) noexcept {
    write(x...);
    putchar_unlocked('\n');
}
};  // namespace kyopro

/**
 * @brief 高速入出力
 */
#line 3 "src/string/rolling_hash.hpp"
#include <random>
#line 5 "src/string/rolling_hash.hpp"
#include <vector>
#line 2 "src/math/gcd.hpp"
#include <cassert>
#include <tuple>
namespace kyopro {
template <typename T> 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<T>(__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 <typename T> 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<T, T>{b, a % b};
        std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q};
        std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q};
    }
    return a;
}
};  // namespace kyopro
#line 3 "src/math/mod_pow.hpp"
namespace kyopro {

/**
 * @brief バイナリ法
 */
template <typename T>
constexpr T mod_pow(internal::double_size_uint_t<T> base, T exp, T mod) {
    internal::double_size_uint_t<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<u64>(1) << 30) - 1;
    static constexpr u64 msk61 = (static_cast<u64>(1) << 31) - 1;
    const std::string str;
    std::vector<u64> _hash, _pow;
    
    static constexpr u64 mod = (static_cast<u64>(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<u64> 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<uint64_t, int> 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);
}