結果
問題 | No.430 文字列検索 |
ユーザー |
![]() |
提出日時 | 2019-10-29 13:49:09 |
言語 | C++11(廃止可能性あり) (gcc 13.3.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#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;}