結果

問題 No.430 文字列検索
ユーザー ToshokahnToshokahn
提出日時 2019-10-29 13:49:09
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 898 ms / 2,000 ms
コード長 1,771 bytes
コンパイル時間 1,127 ms
コンパイル使用メモリ 165,992 KB
実行使用メモリ 7,936 KB
最終ジャッジ日時 2024-08-15 16:23:26
合計ジャッジ時間 12,306 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 872 ms
7,836 KB
testcase_01 AC 6 ms
7,204 KB
testcase_02 AC 873 ms
7,832 KB
testcase_03 AC 871 ms
7,832 KB
testcase_04 AC 878 ms
7,768 KB
testcase_05 AC 6 ms
7,152 KB
testcase_06 AC 5 ms
7,104 KB
testcase_07 AC 5 ms
7,104 KB
testcase_08 AC 5 ms
7,068 KB
testcase_09 AC 10 ms
7,624 KB
testcase_10 AC 6 ms
7,168 KB
testcase_11 AC 8 ms
7,272 KB
testcase_12 AC 879 ms
7,760 KB
testcase_13 AC 879 ms
7,824 KB
testcase_14 AC 878 ms
7,936 KB
testcase_15 AC 873 ms
7,920 KB
testcase_16 AC 878 ms
7,764 KB
testcase_17 AC 898 ms
7,756 KB
testcase_18 AC 892 ms
7,816 KB
権限があれば一括ダウンロードができます

ソースコード

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