結果
問題 | No.430 文字列検索 |
ユーザー |
|
提出日時 | 2020-09-02 09:58:15 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 230 ms / 2,000 ms |
コード長 | 2,302 bytes |
コンパイル時間 | 3,506 ms |
コンパイル使用メモリ | 116,444 KB |
最終ジャッジ日時 | 2025-01-14 03:32:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#include <cassert>#include <cstring>#include <iostream>#include <unordered_map>#include <vector>using namespace std;using u64 = uint64_t;u64 uz = time(NULL);inline u64 xorshift64() {uz ^= uz << 18;uz ^= uz >> 19;uz ^= uz << 19;return uz;}template <class T>class rolling_hash {static constexpr u64 M = 0x7fff'ffff'ffff'ffe7,M2 = 0x0f5c'28f5'c28f'5c29,R2 = static_cast<u64>(-__uint128_t(M) % M);static constexpr u64 norm(u64 a) {return a < M ? a : a - M;}static constexpr u64 mod_add(u64 a, u64 b) {return norm(a + b);}static constexpr u64 mod_sub(u64 a, u64 b) {return a < b ? a - b + M : a - b;}static constexpr u64 MR(__uint128_t t) {return norm(u64((__uint128_t(u64(t) * M2) * M + t) >> 64));}static constexpr u64 init(__uint128_t x) {return MR(x * R2);}static constexpr u64 mod_mul(u64 x, __uint128_t y) {return MR(x * y);}T s;u64 b64;size_t n;vector<u64> B, H;public:rolling_hash() {}~rolling_hash() noexcept {}explicit rolling_hash(const T &_s, u64 seed=xorshift64()) : s(_s), b64(seed % M), n(s.size()) {B.resize(n+1);H.resize(n+1);B[0] = init(1);for(size_t i=0; i<n; ++i) {B[i+1] = mod_mul(B[i], b64);H[i+1] = mod_add(mod_mul(H[i], b64), s[i]);}}u64 calc_hash(size_t l, size_t r) const { // [l, r]. つまり l も r も含む。1-indexed.assert(l <= r);assert(l <= n && r <= n); // if(l > n || r > n) { return -1; }return calc_hash2(l, r-l+1);}u64 calc_hash2(size_t l, size_t len) const { // l から len 文字。1-indexed.assert(1 <= len);assert(l <= n && l+len <= n+1);return mod_sub(H[l+len-1], mod_mul(B[len], H[l-1]));}};int main(void) {cin.tie(nullptr); ios::sync_with_stdio(false);string s; int m; cin >> s >> m;u64 seed = xorshift64();rolling_hash rh(s, seed);unordered_map<u64, int> mp;for(size_t i=1, n=s.size(); i<=n; ++i) {for(size_t len=1; len<=10 && i+len<=n+1; ++len) {++mp[rh.calc_hash2(i, len)];}}int res = 0;for(int i=0; i<m; ++i) {string ci; cin >> ci;rolling_hash rh2(ci, seed);res += mp[rh2.calc_hash(1, ci.size())];}cout << res << '\n';return 0;}