結果
問題 | No.430 文字列検索 |
ユーザー | lynmisakura |
提出日時 | 2022-03-21 16:47:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 2,793 bytes |
コンパイル時間 | 1,972 ms |
コンパイル使用メモリ | 215,128 KB |
実行使用メモリ | 28,672 KB |
最終ジャッジ日時 | 2024-11-10 00:59:45 |
合計ジャッジ時間 | 3,473 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 270 ms
28,672 KB |
testcase_02 | AC | 15 ms
5,888 KB |
testcase_03 | AC | 15 ms
5,888 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 246 ms
28,416 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 14 ms
6,016 KB |
testcase_11 | AC | 73 ms
9,600 KB |
testcase_12 | AC | 74 ms
9,600 KB |
testcase_13 | AC | 73 ms
9,600 KB |
testcase_14 | AC | 58 ms
8,064 KB |
testcase_15 | AC | 48 ms
7,168 KB |
testcase_16 | AC | 17 ms
6,016 KB |
testcase_17 | AC | 16 ms
5,888 KB |
ソースコード
// code by lynmisakura. wish to be accepted! #include<bits/stdc++.h> using namespace std; #ifdef LOCAL #include "/Users/debug.h" #else #define debug(...) 42 #endif using ll = long long; using ull = unsigned long long; using ld = long double; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using pi = pair<int, int>; using pl = pair<ll, ll>; using vpi = vector<pi>; using vpl = vector<pl>; #define REP(i, N) for(int i = 0;i < N;i++) #define mp make_pair #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() template<class T> void init(vector<T> &a, int N) { a.resize(N); } template<class T> void init(vector<T> &a, int N, T val) { a.assign(N, val); } template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } else { return false; } } template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } else { return false; } } template<class T> T extgcd(T a, T b, T &x, T &y) { T d = a; if (b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } template<class T> T modinv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; } template<class S, int64_t P, int64_t B = 31> class rolling_hash { public: rolling_hash(vector<S> &a) : a(a) { init(); } rolling_hash(std::string &s, char c = 'a') { a.resize((int)s.length()); for (int i = 0; i < (int)s.length(); i++) { a[i] = s[i] - c + 1; } init(); } void init() { N = a.size(); hash.assign(N + 1, 0); b_inv.assign(N + 1, 0); long b_pow = 1; for (int i = 0; i < N; i++) { hash[i + 1] = (hash[i] + a[i] * b_pow) % P; b_pow = (b_pow * B) % P; } b_inv[0] = 1; b_inv[1] = modinv(B, P); for (int i = 2; i <= N; i++) { b_inv[i] = (b_inv[i - 1] * b_inv[1]) % P; } } int64_t f(int l, int r) { int64_t res = (hash[r] - hash[l] + P) % P; res = (res * b_inv[l]) % P; return res; } int64_t f_all(){ return f(0,N); } private: int N; vector<S> a; vector<int64_t> hash; vector<int64_t> b_inv; }; int main() { string s; cin >> s; int len = s.length(); rolling_hash<ll,998244353,31> rh_1(s,'A'); rolling_hash<ll,int(1e9)+7,31> rh_2(s,'A'); map<pl,int> m; REP(i,len)for(int j = 1;j <= 10 && i + j <= len;j++){ ll h_1 = rh_1.f(i,i + j); ll h_2 = rh_2.f(i,i + j); m[mp(h_1,h_2)]++; } ll ans = 0; int q; cin >> q; while(q--){ string c; cin >> c; rolling_hash<ll,998244353,31> rh_3(c,'A'); rolling_hash<ll,int(1e9)+7,31> rh_4(c,'A'); ll h_3 = rh_3.f_all(); ll h_4 = rh_4.f_all(); ans += m[mp(h_3,h_4)]; } cout << ans << '\n'; }