結果
問題 | No.430 文字列検索 |
ユーザー | essence0826 |
提出日時 | 2023-09-12 00:27:31 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,498 bytes |
コンパイル時間 | 2,780 ms |
コンパイル使用メモリ | 258,648 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-10 01:07:19 |
合計ジャッジ時間 | 3,714 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | AC | 20 ms
5,248 KB |
testcase_03 | AC | 20 ms
5,248 KB |
testcase_04 | WA | - |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | WA | - |
testcase_08 | AC | 20 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | WA | - |
testcase_11 | AC | 42 ms
5,248 KB |
testcase_12 | AC | 42 ms
5,248 KB |
testcase_13 | AC | 42 ms
5,248 KB |
testcase_14 | AC | 38 ms
5,248 KB |
testcase_15 | AC | 34 ms
5,248 KB |
testcase_16 | AC | 20 ms
5,248 KB |
testcase_17 | AC | 19 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define BE(x) x.begin(), x.end() using ll = long long; template<class T> using vec = vector<T>; class rolling_hash { private: using ull = uint64_t; static const ull max_a = CHAR_MAX; // the max element of sequence to be hashed static const int base_n = 2; // number of bases static constexpr ull p = (1ull<<61)-1ull; static const ull p_root = 37ull; static ull base[base_n]; static vector<ull> base_pow[base_n]; vector<ull> hash[base_n]; ull mod(ull x) { ull res = (x>>61) + (x&p); if (res >= p) res -= p; return res; } ull mul(ull a, ull b) { constexpr ull mask31 = (1ull<<31)-1ull; constexpr ull mask30 = (1ull<<30)-1ull; const ull au = a>>31; const ull bu = b>>31; const ull ad = a&mask31; const ull bd = b&mask31; const ull mid = au*bd + bu*ad; const ull midu = mid>>30; const ull midd = mid&mask30; return mod(au*bu*2ull + midu+(midd<<31) + ad*bd); } ull root_pow(ull ex) { ull res = 1ull; ull bin = p_root; while (ex) { if (ex&1ull) res = mul(res, bin); bin = mul(bin, bin); ex >>= 1; } return res; } void set_base() { random_device rd; mt19937_64 rand(rd()); for (ull &e : base) { while (!e) { const ull ex = rand(); if (gcd(ex, p-1ull) != 1ull) continue; const ull b = root_pow(ex); if (b <= max_a+1ull) continue; if (find(base, base+base_n, b) != base+base_n) continue; e = b; } } } void set_base_pow(const int n) { const int prev_size = base_pow[0].size(); for (int i = 0; i < base_n; ++i) { base_pow[i].resize(n); base_pow[i][0] = 1ull; for (int j = prev_size+1; j < n; ++j) { base_pow[i][j] = mul(base_pow[i][j-1], base[i]); } } } public: template<typename T> rolling_hash(T arr) { if (!base[0]) set_base(); const int n = arr.size(); if (base_pow[0].size() < (size_t)n) set_base_pow(n+1); for (int i = 0; i < base_n; ++i) { hash[i].resize(n+1); hash[i][0] = 0ull; for (int j = 0; j < n; ++j) { hash[i][j+1] = mod(mul(hash[i][j],base[i])+(ull)arr[j]+1ull); } } } array<ull,base_n> subseq(int l, int r) { // 0-indexed, hankai-kukan array<ull,base_n> res; for (int i = 0; i < base_n; ++i) { ull h = hash[i][r] + p-mul(hash[i][l],base_pow[i][r-l]); if (h >= p) h -= p; res[i] = h; } return res; } using result = array<ull,base_n>; }; uint64_t rolling_hash::base[]; vector<uint64_t> rolling_hash::base_pow[]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; int m; cin >> s >> m; map<rolling_hash::result,int> p; while (m--) { string t; cin >> t; auto&& h = rolling_hash(t).subseq(0,t.size()); ++p[h]; } int c = 0; rolling_hash sh(s); int n = s.size(); for (int i = 1; i <= 10; ++i) for (int j = 0; j+i <= n; ++j) { auto&& h = sh.subseq(j,j+i); if (p.contains(h)) c += p[h]; } cout << c << '\n'; }