結果
問題 | No.430 文字列検索 |
ユーザー | Ramurata |
提出日時 | 2023-12-03 15:20:25 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 2,424 bytes |
コンパイル時間 | 3,156 ms |
コンパイル使用メモリ | 256,940 KB |
実行使用メモリ | 23,136 KB |
最終ジャッジ日時 | 2024-11-10 01:07:50 |
合計ジャッジ時間 | 3,967 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 124 ms
23,136 KB |
testcase_02 | AC | 14 ms
5,248 KB |
testcase_03 | AC | 15 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 119 ms
23,136 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 7 ms
5,248 KB |
testcase_11 | AC | 29 ms
6,476 KB |
testcase_12 | AC | 30 ms
6,476 KB |
testcase_13 | AC | 31 ms
6,476 KB |
testcase_14 | AC | 24 ms
5,348 KB |
testcase_15 | AC | 22 ms
5,248 KB |
testcase_16 | AC | 15 ms
5,248 KB |
testcase_17 | AC | 14 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; /** * @brief RollingHash */ struct RollingHash { private: static const uint64_t mod = (1ull << 61ull) - 1; using uint128_t = __uint128_t; std::vector<uint64_t> power; const uint64_t base; static inline uint64_t add(uint64_t a, uint64_t b) { if((a += b) >= mod) a -= mod; return a; } static inline uint64_t mul(uint64_t a, uint64_t b) { uint128_t c = (uint128_t)a * b; return add(c >> 61, c & mod); } static inline uint64_t generate_base() { std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution< uint64_t > rand(1, RollingHash::mod - 1); return rand(mt); } inline void expand(size_t sz) { if(power.size() < sz + 1) { int pre_sz = (int)power.size(); power.resize(sz + 1); for(int i = pre_sz - 1; i < sz; i++) { power[i + 1] = mul(power[i], base); } } } public: RollingHash(uint64_t base = generate_base()) : base(base), power{1} {} std::vector<uint64_t> build(const std::string &s) const { int sz = s.size(); std::vector<uint64_t> hashed(sz + 1); for(int i = 0; i < sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } template<typename T> std::vector<uint64_t> build(const std::vector<T> &s) const { int sz = s.size(); std::vector<uint64_t> hashed(sz + 1); for(int i = 0; i < sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } uint64_t hash(const std::vector<uint64_t> &s, int l, int r) { expand(r - l); return add(s[r], mod - mul(s[l], power[r - l])); } uint64_t all_hash(const std::vector<uint64_t> &s) { return s.back(); } }; int main() { RollingHash rh; string S; int M; cin >> S >> M; auto hash = rh.build(S); unordered_map<uint64_t, int> cnt; for(int i = 0; i < S.size(); ++i) { for(int j = 0; j < 10; ++j) { if(i + j < S.size()) cnt[rh.hash(hash, i, i + j + 1)]++; } } string T; int ans = 0; for(int i = 0; i < M; ++i) { cin >> T; ans += cnt[rh.all_hash(rh.build(T))]; } cout << ans << endl; }