結果

問題 No.430 文字列検索
コンテスト
ユーザー Toshokahn
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0