結果
| 問題 | 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 |
| コンパイル時間 | 2,160 ms |
| コンパイル使用メモリ | 134,136 KB |
| 実行使用メモリ | 16,604 KB |
| 最終ジャッジ日時 | 2023-10-23 06:41:39 |
| 合計ジャッジ時間 | 3,685 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 4 ms
12,120 KB |
| testcase_01 | AC | 23 ms
16,604 KB |
| testcase_02 | AC | 14 ms
16,376 KB |
| testcase_03 | AC | 14 ms
16,600 KB |
| testcase_04 | AC | 4 ms
11,960 KB |
| testcase_05 | AC | 4 ms
12,080 KB |
| testcase_06 | AC | 3 ms
9,848 KB |
| testcase_07 | AC | 4 ms
12,332 KB |
| testcase_08 | AC | 21 ms
16,600 KB |
| testcase_09 | AC | 4 ms
12,564 KB |
| testcase_10 | AC | 8 ms
16,140 KB |
| testcase_11 | AC | 18 ms
16,604 KB |
| testcase_12 | AC | 18 ms
16,600 KB |
| testcase_13 | AC | 18 ms
16,600 KB |
| testcase_14 | AC | 16 ms
16,604 KB |
| testcase_15 | AC | 16 ms
16,600 KB |
| testcase_16 | AC | 14 ms
16,380 KB |
| testcase_17 | AC | 14 ms
16,340 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);
}