結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 AC2K
|
| 提出日時 | 2023-05-01 16:18:16 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 19 ms / 2,000 ms |
| コード長 | 8,771 bytes |
| コンパイル時間 | 1,333 ms |
| コンパイル使用メモリ | 131,900 KB |
| 実行使用メモリ | 16,512 KB |
| 最終ジャッジ日時 | 2024-11-10 01:06:18 |
| 合計ジャッジ時間 | 1,970 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 14 |
ソースコード
#include <iostream>
#line 1 "test/yuki/No430.test.cpp"
#define PROBLEM "https://yukicoder.me/submissions/865256"
#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 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<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.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';
}