#927035 (C++17) No.430 文字列検索

提出ソース

結果

問題	No.430 文字列検索
ユーザー	2 Z0l
提出日時	2023-11-09 02:01:55
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	514 ms / 2,000 ms
コード長	6,284 bytes
コンパイル時間	8,579 ms
コンパイル使用メモリ	499,396 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2023-11-09 02:02:10
合計ジャッジ時間	13,562 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	485 ms 6,676 KB
testcase_02	AC	487 ms 6,676 KB
testcase_03	AC	493 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	2 ms 6,676 KB
testcase_08	AC	4 ms 6,676 KB
testcase_09	AC	2 ms 6,676 KB
testcase_10	AC	3 ms 6,676 KB
testcase_11	AC	484 ms 6,676 KB
testcase_12	AC	514 ms 6,676 KB
testcase_13	AC	485 ms 6,676 KB
testcase_14	AC	513 ms 6,676 KB
testcase_15	AC	489 ms 6,676 KB
testcase_16	AC	487 ms 6,676 KB
testcase_17	AC	497 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128_t lll;
typedef string str;

#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using Bint = mp::cpp_int; // 多倍長整数
using Real = mp::number<mp::cpp_dec_float<1024>>;

#define MOD (998244353LL)
#define INF (2147483647/3)
#define INFS (-2147483647/3)
#define LLINF (9223372036854775807LL/3)
#define LLINFS (-9223372036854775807LL/3)
#define rep(i, N) for (ll i=0; i<(ll)(N); ++i)
#define rrep(i, N) for (ll i=N-1; i>=0LL; --i)
#define all(A) A.begin(),A.end()

#define elif else if
#define RET return 0
#define CIN(x) cin >> x
#define COUT(x) cout << x << endl
#define COUTS(x) cout << x << " "
#define ENDL cout << endl
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define YESRET cout << "Yes" << endl; RET
#define NORET cout << "No" << endl; RET

#define LL(N) ll N; cin >> N
#define __INT1(A) LL(A)
#define __INT2(A,B) __INT1(A);__INT1(B)
#define __INT3(A,B,C) __INT2(A,B);__INT1(C)
#define __INT4(A,B,C,D) __INT3(A,B,C);__INT1(D)
#define __INTSEL(_1,_2,_3,_4,_5,...) _5
#define INT(...) __INTSEL(__VA_ARGS__,__INT4,__INT3,__INT2,__INT1)(__VA_ARGS__)

#define __STR1(A) str A; cin >> A
#define __STR2(A,B) __STR1(A);__STR1(B)
#define __STR3(A,B,C) __STR2(A,B);__STR1(C)
#define __STR4(A,B,C,D) __STR3(A,B,C);__STR1(D)
#define __STRSEL(_1,_2,_3,_4,_5,...) _5
#define STR(...) __STRSEL(__VA_ARGS__,__STR4,__STR3,__STR2,__STR1)(__VA_ARGS__)

#define __MIN1(A) min(A,LLINF)
#define __MIN2(A,B) min(__MIN1(A),B)
#define __MIN3(A,B,C) min(__MIN2(A,B),C)
#define __MIN4(A,B,C,D) min(__MIN3(A,B,C),D)
#define __MINSEL(_1,_2,_3,_4,_5,...) _5
#define MIN(...) __MINSEL(__VA_ARGS__,__MIN4,__MIN3,__MIN2,__MIN1)(__VA_ARGS__)

#define __MAX1(A) max(A,LLINFS)
#define __MAX2(A,B) max(__MAX1(A),B)
#define __MAX3(A,B,C) max(__MAX2(A,B),C)
#define __MAX4(A,B,C,D) max(__MAX3(A,B,C),D)
#define __MAXSEL(_1,_2,_3,_4,_5,...) _5
#define MAX(...) __MAXSEL(__VA_ARGS__,__MAX4,__MAX3,__MAX2,__MAX1)(__VA_ARGS__)

#define PII pair<ll,ll>
#define PIS pair<ll,str>
#define PSI pair<str,ll>
#define PSS pair<str,str>

#define SLL set<ll>
#define SINT SLL
#define SSTR set<str>
#define SPLL set<pair<ll,ll>>
#define SPII SPLL
#define SPLS set<pair<ll,str>>
#define SPIS SPLS
#define SPSL set<pair<str,ll>>
#define SPSI SPSL

#define PQL priority_queue<ll>
#define PQI PQL
#define RPQL priority_queue<ll, vector<ll>, greater<ll>>
#define RPQI RPQL

#define VLL vector<ll>
#define VINT VLL
#define VSTR vector<str>
#define VVLL(A, H, W) vector<VLL> A(H,VLL(W))
#define VVINT(A, H, W) VVLL(A, H, W)
#define VVSTR(A, H, W) vector<VSTR> A(H,VSTR(W))

#define VIN(A,N) VINT A(N); rep(__VIN_i,N) cin >> A[__VIN_i]
#define VST(A,N) VSTR A(N); rep(__VST_i,N) cin >> A[__VST_i]
#define VIN2(A,B,N) VINT A(N); VINT B(N); rep(__VIN_i,N) cin >> A[__VIN_i] >> B[__VIN_i]

#define VPII(A,N) vector<PII> A(N)
#define VPIS(A,N) vector<PIS> A(N)
#define VPSI(A,N) vector<PSI> A(N)
#define VPSS(A,N) vector<PSS> A(N)

#define VPIIN(A,N) VPII(A,N); rep(__VPIIN_i,N) cin >> A[__VPIIN_i].first >> A[__VPIIN_i].second

#define ins(a) insert(a)
#define pb(a) push_back(a)
#define SORT(A) sort(all(A))
#define SSORT(A) stable_sort(all(A))
#define REV(A) reverse(all(A))
#define INCR(A) rep(__INCR_i,A.size()) ++A[__INCR_i]
#define DECR(A) rep(__DECR_i,A.size()) --A[__DECR_i]

// N以上の最小値
#define LB(A,N) *lower_bound(all(A), N)
// Nを超える最小値
#define UB(A,N) *upper_bound(all(A), N)

#define DEBUG COUT("DEBUG")
#define DEB(x) cout << "DEB " << x << endl

// AのB乗
ll POW(ll A,ll B) {
    ll __POW = 1;
    ll __Asub = A;
    ll __Bsub = B;
    while(__Bsub > 0) {
      if(__Bsub & 1) __POW *= __Asub;//Bの下からi番目のbitが1ならば、A^(2^i)をかける
      __Asub *= __Asub;
      __Bsub >>= 1;
    }
    return __POW;
}
// AのB乗(mod998)
ll MPOW(ll A,ll B) {
    ll __MPOW = 1;
    ll __Asub = A;
    ll __Bsub = B;
    while(__Bsub > 0) {
      if(__Bsub & 1) __MPOW = __MPOW * __Asub % MOD;
      __Asub = __Asub * __Asub % MOD;
      __Bsub >>= 1;
    }
    return __MPOW;
}

// 二分探索(めぐる式)
// vector<ll> A:sort済み整数列(長さN)
// A_i>=Kであるような最小のi
// すべてK未満ならNを返す
ll BinarySearch(ll N,vector<ll> A,ll K) {
  ll __BS_ok = N-1;
  ll __BS_ng = -1;
  if(A[N-1] < K) return N;
  while(__BS_ok - __BS_ng != 1) {
    ll __BS_now = (__BS_ok + __BS_ng) / 2;
    if(A[__BS_now] >= K) __BS_ok = __BS_now;
    else __BS_ng = __BS_now;
  }
  return __BS_ok;
}

// N頂点M辺のグラフが二部グラフかどうか
// vector<pair<ll,ll>> A:辺一覧(長さM,0-indexed)
bool IsBipartiteGraph(ll N,ll M,vector<pair<ll,ll>> A) {
  dsu d(N*2);
  rep(__IBG_i,M) {
    d.merge((A[__IBG_i].first),(A[__IBG_i].second)+N);
    d.merge((A[__IBG_i].first)+N,(A[__IBG_i].second));
  }
  rep(__IBG_i,N) {
    if(d.same(__IBG_i,__IBG_i+N)) return 0;
  }
  return 1;
}

// ローリングハッシュ
// Sが連続部分文字列としてTをもつならtrue
ll rolling_hash(str S, str T){
  ll RH_ans=0;
  #define B1 100000007
  #define B2 1000000007
  ll RH_SL=S.length();
  ll RH_TL=T.length();

  // B^mを用意する
  ull pow_B_m_1 = 1, pow_B_m_2 = 1;
  for(int RH_k = 0; RH_k < RH_TL; RH_k++){
    pow_B_m_1 *= B1, pow_B_m_2 *= B2;
  }

  // sの先頭m文字のハッシュ値shと,tのハッシュ値th
  ull sh1 = 0, sh2 = 0, th1 = 0, th2 = 0;
  for(int RH_k = 0; RH_k < RH_TL; RH_k++){
    th1 = th1 * B1 + T[RH_k], th2 = th2 * B2 + T[RH_k];
    sh1 = sh1 * B1 + S[RH_k], sh2 = sh2 * B2 + S[RH_k];
  }

  // sをずらしてハッシュ値を更新
  for(int RH_k = 0; RH_k <= RH_SL - RH_TL; RH_k++){
    // shのハッシュ==thのハッシュならtrue
    if(sh1 == th1 && sh2 == th2) ++RH_ans;
    if(RH_k < RH_SL - RH_TL){
      sh1 = sh1 * B1 + S[RH_TL + RH_k] - S[RH_k] * pow_B_m_1;
      sh2 = sh2 * B2 + S[RH_TL + RH_k] - S[RH_k] * pow_B_m_2;
    }
  }
  return RH_ans;
}


int main() {
  cout << fixed << setprecision(15);
  STR(S);
  INT(M);
  ll ans=0;
  rep(i,M) {
    STR(C);
    ans+=rolling_hash(S,C);
  }
  COUT(ans);
}

yukicoder

結果

テストケース

ソースコード