結果

問題 No.430 文字列検索
ユーザー shirokamishirokami
提出日時 2023-03-13 14:50:24
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,793 ms / 2,000 ms
コード長 4,262 bytes
コンパイル時間 5,516 ms
コンパイル使用メモリ 314,276 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-18 11:05:56
合計ジャッジ時間 24,561 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1,787 ms
4,348 KB
testcase_02 AC 1,793 ms
4,348 KB
testcase_03 AC 1,793 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 9 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 6 ms
4,348 KB
testcase_11 AC 1,790 ms
4,348 KB
testcase_12 AC 1,790 ms
4,348 KB
testcase_13 AC 1,788 ms
4,348 KB
testcase_14 AC 1,792 ms
4,348 KB
testcase_15 AC 1,786 ms
4,348 KB
testcase_16 AC 1,788 ms
4,348 KB
testcase_17 AC 1,782 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
#include <atcoder/all>
using namespace atcoder;
// https://atcoder.github.io/ac-library/production/document_ja/
typedef long long int ll;
typedef long double ld;
const ll mod = 1e9+7;
const ll INF = 9'223'372'036'854'775'807/10;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define Rep(i,a,n) for (ll i = (a); i < (n); ++i)
#define All(a) (a).begin(),(a).end()
#define Pi acos(-1)
using V = vector<ll>;
using P = pair<ll,ll>;
vector<ll> dx = {1, 0, -1, 0, 1, 1, -1, -1};
vector<ll> dy = {0, 1, 0, -1, 1, -1, 1, -1};
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
struct edge{ll to, cost;};
using graph = vector<vector<edge> >;
struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << setprecision(15) << fixed;
  }
} iosetup;
void printvec(vector<int> a) {
  for(ll i = 0; i < a.size(); i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
}

/*
  Rolling Hash
  
  使い方
  RollingHash rh();
  auto s_hash = rh.build(s);
  rh.query(s_hash, l, r) // s[l, r)のハッシュ値
  rh.combine(h1, h2, h2_len) // h1の後ろにh2を連結したときのハッシュ値
  rh.lcp(s_hash, s_l, s_r, t_hash, t_l, t_r) // s[s_l, s_r)とt[t_l, t_r)の最長共通接頭辞の長さ

  計算量
  build() : O(|S|)
  query(), combine() : O(1)
  lcp() : O(log|S|)

  https://ei1333.github.io/library/string/rolling-hash.hpp
*/
struct RollingHash {
    static constexpr uint64_t mod = (1ull << 61ull) - 1;
    vector<uint64_t> power;
    const uint64_t base;

    static inline uint64_t add(uint64_t a, uint64_t b) {
        uint64_t res = a + b;
        if (res >= mod) res -= mod;
        return res;
    }

    static inline uint64_t mul(uint64_t a, uint64_t b) {
        __uint128_t c = (__uint128_t)a * b;
        return add(c >> 61, c & mod);
    }

    static inline uint64_t generate_base() {
        mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<uint64_t> rand(1, RollingHash::mod - 1);
        return rand(mt);
    }

    inline void expand(size_t sz) {
        if (power.size() < sz + 1) {
            int pre_sz = (int)power.size();
            power.resize(sz + 1);
            for (int i = pre_sz - 1; i < sz; i++) {
                power[i+1] = mul(power[i], base);
            }
        }
    }

    explicit RollingHash(uint64_t base = generate_base()) : base(base), power{1} {}

    vector<uint64_t> build(const string &s) {
        int sz = (int)s.size();
        vector<uint64_t> hash(sz + 1);
        for (int i = 0; i < sz; i++) {
            hash[i+1] = add(mul(hash[i], base), s[i]);
        }
        return hash;
    }

    uint64_t query(const vector<uint64_t> &hash, int l, int r) {
        expand(r - l);
        return add(hash[r], mod - mul(hash[l], power[r - l]));
    }

    uint64_t combine(uint64_t h1, uint64_t h2, size_t h2_len) {
        expand(h2_len);
        return add(mul(h1, power[h2_len]), h2);
    }

    int lcp(const vector<uint64_t> &s_hash, int s_l, int s_r, const vector<uint64_t> &t_hash, int t_l, int t_r) {
        int len = min(s_r - s_l, t_r - t_l);
        int low = -1, high = len + 1;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (query(s_hash, s_l, s_l + mid) == query(t_hash, t_l, t_l + mid)) low = mid;
            else high = mid;
        }
        return low;
    }
};


int main() {
  string s;
  cin >> s;
  RollingHash rh;
  auto s_hash = rh.build(s);
  ll s_size = s.size();
  ll q;
  cin >> q;
  ll ans = 0;
  while (q--) {
    string t;
    cin >> t;
    auto t_hash = rh.build(t);
    ll t_size = t.size();
    if (s_size < t_size) {
      continue;
    }
    for (ll i = 0; i <= s_size - t_size; i++) {
      if (rh.query(s_hash, i, i + t_size) == rh.query(t_hash, 0, t_size)) {
        ans++;
      }
    }
  }
  cout << ans << '\n';
}
0