結果
問題 | No.430 文字列検索 |
ユーザー | Manuel1024 |
提出日時 | 2023-01-10 14:10:44 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 835 ms / 2,000 ms |
コード長 | 2,724 bytes |
コンパイル時間 | 1,011 ms |
コンパイル使用メモリ | 95,436 KB |
実行使用メモリ | 9,112 KB |
最終ジャッジ日時 | 2023-08-23 10:13:44 |
合計ジャッジ時間 | 10,347 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 829 ms
7,832 KB |
testcase_02 | AC | 832 ms
8,844 KB |
testcase_03 | AC | 830 ms
8,920 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 22 ms
4,772 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 5 ms
4,376 KB |
testcase_11 | AC | 827 ms
8,788 KB |
testcase_12 | AC | 827 ms
9,112 KB |
testcase_13 | AC | 829 ms
8,904 KB |
testcase_14 | AC | 835 ms
8,944 KB |
testcase_15 | AC | 829 ms
8,868 KB |
testcase_16 | AC | 821 ms
8,868 KB |
testcase_17 | AC | 824 ms
8,844 KB |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <random> using namespace std; using ll = long long; struct RollingHash{ static constexpr ll MOD1 = 998244353; static constexpr ll MOD2 = 1000000007; const ll b1, b2; const vector<ll> hs1, hs2; vector<ll> rev1, rev2; RollingHash(const string &s): b1(rnd()), b2(rnd()), hs1(hash(s, b1, MOD1)), hs2(hash(s, b2, MOD2)){ init(s); } RollingHash(const string &s, ll b1, ll b2): b1(b1), b2(b2), hs1(hash(s, b1, MOD1)), hs2(hash(s, b2, MOD2)){ init(s); } // hash1(s[l, r)), hash2(s[l, r)) pair<ll, ll> get(int l, int r){ return { (hs1[r]-hs1[l]+MOD1)%MOD1*rev1[l]%MOD1, (hs2[r]-hs2[l]+MOD2)%MOD2*rev2[l]%MOD2 }; } vector<ll> hash(const string &s, const ll base, const ll mod){ vector<ll> hs(s.size()+1); ll bm1 = 1; for(int i = 0; i < s.size(); i++){ hs[i+1] = (hs[i]+bm1*s[i])%mod; bm1 *= base; bm1 %= mod; } return hs; } private: static constexpr int bmin = 300; void init(const string &s){ rev1 = vector<ll>(s.size()); ll bm1 = 1; for(int i = 0; i < s.size(); i++){ rev1[i] = mpow1(bm1, MOD1-2); bm1 *= b1; bm1 %= MOD1; } rev2 = vector<ll>(s.size()); ll bm2 = b2; for(int i = 0; i < s.size(); i++){ rev2[i] = mpow2(bm2, MOD2-2); bm2 *= b2; bm2 %= MOD2; } } ll rnd(){ mt19937 mt{random_device{}()}; return mt()%(MOD1-bmin)+bmin; } ll mpow1(ll a, ll x){ ll res = 1; for(; x > 0; x >>= 1){ if(x & 1){ res *= a; res %= MOD1; } a *= a; a %= MOD1; } return res; } ll mpow2(ll a, ll x){ ll res = 1; for(; x > 0; x >>= 1){ if(x & 1){ res *= a; res %= MOD2; } a *= a; a %= MOD2; } return res; } }; int main(){ string s; cin >> s; int m; cin >> m; vector<string> c(m); for(auto &it: c) cin >> it; RollingHash hs(s); vector<RollingHash> hc; for(auto &it: c) hc.emplace_back(it, hs.b1, hs.b2); ll ans = 0; for(int i = 0; i < m; i++){ for(int j = 0; j+c[i].size() <= s.size(); j++){ if(hs.get(j, j+c[i].size()) == hc[i].get(0, c[i].size())){ // cerr << i << " " << j << endl; ans++; } } } cout << ans << endl; return 0; }