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

提出ソース

結果

問題	No.430 文字列検索
ユーザー	AC2K
提出日時	2023-05-01 16:01:19
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	19 ms / 2,000 ms
コード長	9,351 bytes
コンパイル時間	3,368 ms
コンパイル使用メモリ	258,016 KB
実行使用メモリ	16,744 KB
最終ジャッジ日時	2024-04-30 17:33:57
合計ジャッジ時間	4,217 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 12,056 KB
testcase_01	AC	19 ms 16,628 KB
testcase_02	AC	14 ms 16,364 KB
testcase_03	AC	14 ms 16,112 KB
testcase_04	AC	3 ms 11,812 KB
testcase_05	AC	3 ms 11,896 KB
testcase_06	AC	2 ms 9,700 KB
testcase_07	AC	3 ms 12,264 KB
testcase_08	AC	18 ms 16,520 KB
testcase_09	AC	4 ms 12,644 KB
testcase_10	AC	7 ms 15,852 KB
testcase_11	AC	16 ms 16,624 KB
testcase_12	AC	16 ms 16,744 KB
testcase_13	AC	15 ms 16,652 KB
testcase_14	AC	14 ms 16,636 KB
testcase_15	AC	14 ms 16,504 KB
testcase_16	AC	14 ms 16,484 KB
testcase_17	AC	14 ms 16,532 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 2 "src/data-structure/hash_map.hpp"
#include <bits/stl_algobase.h>
#include <chrono>
namespace kyopro {
/// @brief HashMap
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;
    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<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
#line 3 "src/string/rolling_hash.hpp"
#include <random>
#include <string>
#include <vector>
#line 2 "src/math/gcd.hpp"
#include <cassert>
#include <tuple>
namespace kyopro {
template <typename T> constexpr T _gcd(T a, T b) {
    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 == 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 <typename T> 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<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 2 "src/internal/type_traits.hpp"
#include <iostream>
#include <limits>
#include <numeric>
#include <typeinfo>
namespace kyopro {
namespace internal {
/// @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
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> struct int_least {
    static_assert(dgt <= 128, "digit have to be less or equals to 128");
    using type = first_enabled_t<std::enable_if<dgt <= 8, __int8_t>,
                                 std::enable_if<dgt <= 16, __int16_t>,
                                 std::enable_if<dgt <= 32, __int32_t>,
                                 std::enable_if<dgt <= 64, __int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t> >;
};
template <int dgt> struct uint_least {
    static_assert(dgt <= 128, "digit have to be less or equals to 128");
    using type = first_enabled_t<std::enable_if<dgt <= 8, __uint8_t>,
                                 std::enable_if<dgt <= 16, __uint16_t>,
                                 std::enable_if<dgt <= 32, __uint32_t>,
                                 std::enable_if<dgt <= 64, __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>;
};  // namespace internal
};  // namespace kyopro
#line 3 "src/math/mod_pow.hpp"
namespace kyopro {

///@brief mod pow(繰り返しニ乗法)
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 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<ull> 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<ull> 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 2 "src/template.hpp"
#include<bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(x) (x).begin(),(x).end()
#define popcount(x) __builtin_popcount(x)
using i128=__int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = 1e9;
constexpr ll infl = 1e18;
constexpr ld eps = 1e-6;
const long double pi = acos(-1);
constexpr uint64_t MOD = 1e9 + 7;
constexpr uint64_t MOD2 = 998244353;
constexpr int dx[] = { 1,0,-1,0 };
constexpr int dy[] = { 0,1,0,-1 };
template<class T>constexpr inline void chmax(T&x,T y){if(x<y)x=y;}
template<class T>constexpr inline void chmin(T&x,T y){if(x>y)x=y;}
#line 4 "main.cpp"
using namespace std;

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
int main() {
    string s;
    int m;
    cin >> s >> m;
    kyopro::RollingHash S(s);
    kyopro::hash_map<uint64_t, int> hash_count;
    rep(i, s.size()) {
        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++) {
        string c;
        cin >> c;
        ans += hash_count[kyopro::RollingHash(c).get_all()];
    }
    cout << ans << '\n';
}

yukicoder

結果

テストケース

ソースコード