結果

問題 No.430 文字列検索
ユーザー coindarwcoindarw
提出日時 2021-03-05 15:10:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 728 ms / 2,000 ms
コード長 2,244 bytes
コンパイル時間 2,315 ms
コンパイル使用メモリ 209,188 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2024-11-10 00:53:48
合計ジャッジ時間 9,671 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 708 ms
6,912 KB
testcase_02 AC 707 ms
7,424 KB
testcase_03 AC 709 ms
7,424 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 8 ms
5,248 KB
testcase_09 AC 3 ms
5,248 KB
testcase_10 AC 5 ms
5,248 KB
testcase_11 AC 716 ms
7,552 KB
testcase_12 AC 701 ms
7,424 KB
testcase_13 AC 728 ms
7,552 KB
testcase_14 AC 707 ms
7,424 KB
testcase_15 AC 706 ms
7,424 KB
testcase_16 AC 700 ms
7,424 KB
testcase_17 AC 698 ms
7,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
typedef long long ll;
#define rep(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (ll i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (ll i = ((ll)(n)-1); i >= 0; --i)
#define rreps(i, n) for (ll i = ((ll)(n)); i > 0; --i)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define repc2(i, s, n) for (ll i = (s); i <= (ll)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;

const long long M1 = 998244353;
const long long M2 = 1000000007;
const long long B1 = 10007;
const long long B2 = 9973;

template <long long MOD1, long long MOD2, long long BASE1, long long BASE2>
class RollingHash {
   private:
    vector<ll> hash1, power1, hash2, power2;
    using hash = pair<ll, ll>;
    int size;

   public:
    RollingHash() {}
    RollingHash(const string &str) {
        size = str.size();
        hash1 = vector<ll>(size + 1, 0);
        hash2 = vector<ll>(size + 1, 0);
        power1 = vector<ll>(size + 1, 1);
        power2 = vector<ll>(size + 1, 1);
        for (int i = 1; i <= size; i++) {
            hash1[i] = (hash1[i - 1] + str[i - 1]) * BASE1 % MOD1;
            hash2[i] = (hash2[i - 1] + str[i - 1]) * BASE2 % MOD2;
            power1[i] = power1[i - 1] * BASE1 % MOD1;
            power2[i] = power2[i - 1] * BASE2 % MOD2;
        }
    }
    hash get(int l, int r) { return make_pair(((hash1[r] - hash1[l] * power1[r - l]) % MOD1 + MOD1) % MOD1, ((hash2[r] - hash2[l] * power2[r - l]) % MOD2 + MOD2) % MOD2); }

    hash concat(hash h1, hash h2, int h2_length) { return make_pair((h1.first * power1[h2_length] + h2.first) % MOD1, (h1.second * power2[h2_length] + h2.second) % MOD2); }
};

using RH = RollingHash<M1, M2, B1, B2>;

int main() {
    string s;
    int m;
    cin >> s >> m;
    vector<string> v(m);
    rep(i, m) cin >> v.at(i);
    RH srh(s);
    vector<RH> vrh(m);
    rep(i, m) { vrh.at(i) = RH(v.at(i)); }

    int cnt = 0;
    rep(i, m) {
        rep(j, s.size() - v.at(i).size() + 1) {
            if (srh.get(j, j + v.at(i).size()) == vrh.at(i).get(0, v.at(i).size())) {
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}
0