結果
問題 | No.430 文字列検索 |
ユーザー | ゆにぽけ |
提出日時 | 2023-07-29 10:52:49 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,267 ms / 2,000 ms |
コード長 | 2,223 bytes |
コンパイル時間 | 706 ms |
コンパイル使用メモリ | 86,548 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-10 01:07:05 |
合計ジャッジ時間 | 13,814 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1,249 ms
5,248 KB |
testcase_02 | AC | 1,251 ms
5,248 KB |
testcase_03 | AC | 1,245 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 7 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 5 ms
5,248 KB |
testcase_11 | AC | 1,249 ms
5,248 KB |
testcase_12 | AC | 1,244 ms
5,248 KB |
testcase_13 | AC | 1,259 ms
5,248 KB |
testcase_14 | AC | 1,240 ms
5,248 KB |
testcase_15 | AC | 1,267 ms
5,248 KB |
testcase_16 | AC | 1,261 ms
5,248 KB |
testcase_17 | AC | 1,255 ms
5,248 KB |
ソースコード
#include<iostream> #include<random> #include<ctime> #include<vector> #include<cassert> using namespace std; struct RollingHash { static const unsigned long mod = (1UL << 61) - 1; static unsigned long base; int n; vector<unsigned long> hashed,pow; inline unsigned long mul(unsigned long a,unsigned long b) const { unsigned long au = a >> 31; unsigned long ad = a & ((1UL << 31)-1); unsigned long bu = b >> 31; unsigned long bd = b & ((1UL << 31)-1); unsigned long mid = au*bd + bu*ad; unsigned long midu = mid >> 30; unsigned long midd = mid & ((1UL << 30)-1); unsigned long res = au*bu*2 + midu + (midd << 31) + ad*bd; res = (res >> 61) + (res & mod); if(res >= mod) res -= mod; return res; } RollingHash(string &s) { n = (int)s.size(); hashed.resize(n+1); pow.resize(n+1); pow[0] = 1; for(int i = 0;i < n;i++) { pow[i+1] = mul(pow[i],base); hashed[i+1] = mul(hashed[i],base) + s[i]; if(hashed[i+1] >= mod) hashed[i+1] -= mod; } } unsigned long get() const {return get(0,n);} unsigned long get(int l,int r) const { assert(0 <= l && l <= r && r <= n); unsigned long res = hashed[r] + mod - mul(hashed[l],pow[r-l]); if(res >= mod) res -= mod; return res; } unsigned long connect(int l1,int r1,int l2,int r2) const { unsigned long h1 = get(l1,r1); unsigned long h2 = get(l2,r2); unsigned long res = h2 + mul(h1,pow[r2-l2]); if(res >= mod) res -= mod; return res; } }; mt19937_64 mt{(unsigned int)time(nullptr)}; unsigned long RollingHash::base = mt()%RollingHash::mod; string s; int m; int main() { cin >> s >> m; RollingHash H(s); int ans = 0; while(m--) { string c; cin >> c; int l = (int)c.size(); RollingHash h(c); unsigned long x = h.get(); for(int i = 0;i+l <= (int)s.size();i++) { unsigned long y = H.get(i,i+l); if(x == y) ans++; } } cout << ans << endl; }