結果
問題 | No.430 文字列検索 |
ユーザー | Toshokahn |
提出日時 | 2019-10-29 13:49:09 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 921 ms / 2,000 ms |
コード長 | 1,771 bytes |
コンパイル時間 | 1,372 ms |
コンパイル使用メモリ | 164,068 KB |
実行使用メモリ | 7,952 KB |
最終ジャッジ日時 | 2024-11-10 00:36:30 |
合計ジャッジ時間 | 10,876 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
7,208 KB |
testcase_01 | AC | 892 ms
7,828 KB |
testcase_02 | AC | 896 ms
7,748 KB |
testcase_03 | AC | 921 ms
7,776 KB |
testcase_04 | AC | 6 ms
7,248 KB |
testcase_05 | AC | 6 ms
7,268 KB |
testcase_06 | AC | 6 ms
7,148 KB |
testcase_07 | AC | 6 ms
7,196 KB |
testcase_08 | AC | 10 ms
7,612 KB |
testcase_09 | AC | 6 ms
7,216 KB |
testcase_10 | AC | 8 ms
7,284 KB |
testcase_11 | AC | 897 ms
7,860 KB |
testcase_12 | AC | 887 ms
7,772 KB |
testcase_13 | AC | 904 ms
7,840 KB |
testcase_14 | AC | 903 ms
7,860 KB |
testcase_15 | AC | 906 ms
7,920 KB |
testcase_16 | AC | 905 ms
7,828 KB |
testcase_17 | AC | 901 ms
7,952 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) #define repp(i, a, b) for (int i = a; i <= (b); ++i) #define sz(x) ((int)(x).size()) /* ------------------------------------- */ typedef unsigned long long ull; const int MAX_LENGTH = 500000; const ull MASK30 = (1ULL << 30) - 1; const ull MASK31 = (1ULL << 31) - 1; const ull MODrh = (1ULL << 61) - 1; const ull POSITIVIZER = MODrh * ((1ULL << 3) - 1); unsigned int Base; vector<ull> powMemo(MAX_LENGTH + 1); ull Mul(ull l, ull r) { ull lu = l >> 31; ull ld = l & MASK31; ull ru = r >> 31; ull rd = r & MASK31; ull middleBit = ld * ru + lu * rd; return ((lu * ru) << 1) + ld * rd + ((middleBit & MASK30) << 31) + (middleBit >> 30); } ull CalcMod(ull val) { val = (val & MODrh) + (val >> 61); if (val > MODrh) val -= MODrh; return val; } void init_RH() { srand(time(NULL)); Base = rand() % RAND_MAX + 129; powMemo[0] = 1; repp(i, 1, sz(powMemo) - 1) { powMemo[i] = CalcMod(Mul(powMemo[i - 1], Base)); } } struct RollingHash { vector<ull> hash; RollingHash(string s) { hash = vector<ull>(sz(s) + 1); rep(i, sz(s)) { hash[i + 1] = CalcMod(Mul(hash[i], Base) + s[i]); } } ull Slice(int begin, int length) { return CalcMod(hash[begin + length] + POSITIVIZER - Mul(hash[begin], powMemo[length])); } }; int main() { init_RH(); string S; cin >> S; int M; cin >> M; vector<string> C(M); rep(i, M) cin >> C[i]; RollingHash RS(S); int ans = 0; rep(i, M) { RollingHash RC(C[i]); int size = sz(C[i]); ull Chash = RC.Slice(0, size); rep(j, sz(S) - size + 1) { if (RS.Slice(j, size) == Chash) ans++; } } cout << ans << endl; }