#831584 (C++14) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: penguin8331
• 提出日時: 2023-01-08 16:54:54
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,344 ms / 2,000 ms
• コード長: 8,608 bytes
• コンパイル時間: 3,595 ms
• コンパイル使用メモリ: 389,084 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-10 01:03:33
• 合計ジャッジ時間: 17,514 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1,322 ms; 5,248 KB
testcase_02	AC	1,339 ms; 5,248 KB
testcase_03	AC	1,331 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	7 ms; 5,248 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	5 ms; 5,248 KB
testcase_11	AC	1,336 ms; 5,248 KB
testcase_12	AC	1,331 ms; 5,248 KB
testcase_13	AC	1,339 ms; 5,248 KB
testcase_14	AC	1,329 ms; 5,248 KB
testcase_15	AC	1,331 ms; 5,248 KB
testcase_16	AC	1,344 ms; 5,248 KB
testcase_17	AC	1,323 ms; 5,248 KB

ソースコード

#pragma region KCLC
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using Bint = boost::multiprecision::cpp_int;
using Real = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1024>>;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define elif else if
#define updiv(N, X) ((N + X - 1) / X)
#define sigma(a, b) ((a + b) * (b - a + 1) / 2)
#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...)
#endif
struct fast_ios {
    fast_ios() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    };
} fast_ios_;
template <typename T>
inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }

template <int MOD>
struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator-() const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator+(const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator-(const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator*(const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator/(const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator+=(const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator-=(const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator*=(const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator/=(const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator==(const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator!=(const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator>>(istream& is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator<<(ostream& os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {
        if (n == 0) return 1;
        if (n < 0) return modpow(modinv(r), -n);
        auto t = modpow(r, n / 2);
        t = t * t;
        if (n & 1) t = t * r;
        return t;
    }
    friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
    }
};

template <class T>
struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int modular = fact_[0].getmod();
        for (int i = 2; i < n; i++) {
            fact_[i] = fact_[i - 1] * i;
            inv_[i] = -inv_[modular % i] * (modular / i);
            finv_[i] = finv_[i - 1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n - k];
    }
    constexpr T hom(int n, int k) const noexcept {
        n += k - 1;
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n - k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

long long mypow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long double dis(pair<long long, long long> a, pair<long long, long long> b) {
    return sqrt(pow((ld)a.first - b.first, 2) + pow((ld)a.second - b.second, 2));
}

long long nCk(int n, int k) {
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res *= (n - k + i) / i;
    }
    return res;
}
#pragma endregion KCLC
//----------------------------------------------------------------------------
constexpr int inf = 1 << 30;
constexpr ll INF = 1LL << 60;
constexpr int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int mod = 998244353;
constexpr int MOD = 1e9 + 7;
using mint = Fp<mod>;
BiCoef<mint> bc;

struct RollingHash {
    static const uint64_t mod = (1ull << 61ull) - 1;
    vector<uint64_t> power, hash;
    const uint64_t base;

    // [1, mod)のランダムなbaseを生成
    static inline uint64_t generate_base() {
        mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<uint64_t> rand((uint64_t)1, (uint64_t)mod - 1);
        return rand(engine);
    }

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

    // 乗算 (__uint128_tを使用)
    static inline uint64_t mul(uint64_t a, uint64_t b) {
        __uint128_t c = (__uint128_t)a * b;
        return add(c >> 61, c & mod);
    }

    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} {}

    // 文字列Sのハッシュを返す
    vector<uint64_t> build(string S) {
        vector<uint64_t> hash(S.size() + 1);
        for (int i = 0; i < S.size(); i++) {
            hash[i + 1] = add(mul(hash[i], base), S[i]);
        }
        return hash;
    }

    // hashの[l,r)のハッシュ値を返す
    uint64_t get(vector<uint64_t>& hash, int l, int r) {
        expand(r - l);
        return add(hash[r], mod - mul(hash[l], power[r - l]));
    }

    // ハッシュ値h1と長さh2lenのハッシュ値h2を結合
    uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) {
        expand(h2len);
        return add(mul(h1, power[h2len]), h2);
    }

    //hash1の区間[l1,r1)とhash2の区間[l2,r2)のlcp(最長共通接頭辞)の長さを返す (二部探索を用いる)
    int getLCP(vector<uint64_t>& hash1, int l1, int r1, vector<uint64_t>& hash2, int l2, int r2) {
        int len = min(r1 - l1, r2 - l2);
        int ok = 0;
        int ng = len + 1;
        int mid;
        while (ng - ok > 1) {
            mid = (ok + ng) / 2;
            if (get(hash1, l1, l1 + mid) == get(hash2, l2, l2 + mid))
                ok = mid;
            else
                ng = mid;
        }
        return ok;
    }
};
int main() {
    string s;
    cin>>s;
    int ssiz=s.size();
    RollingHash rh;
    auto shash=rh.build(s);
    int Q;
    cin>>Q;
    int ans=0;
    for(int i=0;i<Q;i++){
        string t;
        cin>>t;
        int tsiz=t.size();
        auto thash=rh.build(t);
        for(int j=0;j<=ssiz-tsiz;j++){
            if(rh.get(shash,j,j+tsiz)==rh.get(thash,0,tsiz)){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}