結果

問題 No.430 文字列検索
ユーザー rniya
提出日時 2023-10-01 19:33:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 341 ms / 2,000 ms
コード長 5,743 bytes
コンパイル時間 1,253 ms
コンパイル使用メモリ 118,716 KB
最終ジャッジ日時 2025-02-17 03:57:38
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::ostream& hash_impl::operator<<(std::ostream&, const modint&)’:
main.cpp:64:90: warning: no return statement in function returning non-void [-Wreturn-type]
   64 |     friend std::ostream& operator<<(std::ostream& os, const modint& rhs) { os << rhs._v; }
      |                                                                                          ^

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/430"

#include <map>
#include <algorithm>
#include <string>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

namespace hash_impl {

static constexpr unsigned long long mod = (1ULL << 61) - 1;

struct modint {
    modint() : _v(0) {}
    modint(unsigned long long v) {
        v = (v >> 61) + (v & mod);
        if (v >= mod) v -= mod;
        _v = v;
    }

    unsigned long long val() const { return _v; }

    modint& operator+=(const modint& rhs) {
        _v += rhs._v;
        if (_v >= mod) _v -= mod;
        return *this;
    }
    modint& operator-=(const modint& rhs) {
        if (_v < rhs._v) _v += mod;
        _v -= rhs._v;
        return *this;
    }
    modint& operator*=(const modint& rhs) {
        __uint128_t t = __uint128_t(_v) * rhs._v;
        t = (t >> 61) + (t & mod);
        if (t >= mod) t -= mod;
        _v = t;
        return *this;
    }
    modint& operator/=(const modint& rhs) { return *this = *this * rhs.inv(); }

    modint operator-() const { return modint() - *this; }

    modint pow(long long n) const {
        assert(0 <= n);
        modint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    modint inv() const { return pow(mod - 2); }

    friend modint operator+(const modint& lhs, const modint& rhs) { return modint(lhs) += rhs; }
    friend modint operator-(const modint& lhs, const modint& rhs) { return modint(lhs) -= rhs; }
    friend modint operator*(const modint& lhs, const modint& rhs) { return modint(lhs) *= rhs; }
    friend bool operator==(const modint& lhs, const modint& rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const modint& lhs, const modint& rhs) { return lhs._v != rhs._v; }
    friend std::ostream& operator<<(std::ostream& os, const modint& rhs) { os << rhs._v; }

  private:
    unsigned long long _v;
};

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

modint base(generate_base());
std::vector<modint> power{1};

modint get_pow(int n) {
    if (n < int(power.size())) return power[n];
    int m = power.size();
    power.resize(n + 1);
    for (int i = m; i <= n; i++) power[i] = power[i - 1] * base;
    return power[n];
}

};  // namespace hash_impl

struct Hash {
    using mint = hash_impl::modint;
    mint x;
    int len;

    Hash() : x(0), len(0) {}
    Hash(mint x, int len) : x(x), len(len) {}

    Hash& operator+=(const Hash& rhs) {
        x = x * hash_impl::get_pow(rhs.len) + rhs.x;
        len += rhs.len;
        return *this;
    }
    Hash operator+(const Hash& rhs) { return *this += rhs; }
    bool operator==(const Hash& rhs) { return x == rhs.x and len == rhs.len; }
};

struct ReversibleHash {
    using mint = hash_impl::modint;
    mint x, rx;
    int len;

    ReversibleHash() : x(0), rx(0), len(0) {}
    ReversibleHash(mint x) : x(x), rx(x), len(1) {}
    ReversibleHash(mint x, mint rx, int len) : x(x), rx(rx), len(len) {}

    ReversibleHash rev() const { return ReversibleHash(rx, x, len); }

    ReversibleHash operator+=(const ReversibleHash& rhs) {
        x = x * hash_impl::get_pow(rhs.len) + rhs.x;
        rx = rx + rhs.rx * hash_impl::get_pow(len);
        len += rhs.len;
        return *this;
    }
    ReversibleHash operator+(const ReversibleHash& rhs) { return *this += rhs; }
    bool operator==(const ReversibleHash& rhs) { return x == rhs.x and rx == rhs.rx and len == rhs.len; }
};

struct RollingHash {
    using mint = hash_impl::modint;

    RollingHash() : power{mint(1)} {}

    template <typename T> std::vector<mint> build(const T& s) const {
        int n = s.size();
        std::vector<mint> hash(n + 1);
        hash[0] = 0;
        for (int i = 0; i < n; i++) hash[i + 1] = hash[i] * base + s[i];
        return hash;
    }

    template <typename T> mint get(const T& s) const {
        mint res = 0;
        for (const auto& x : s) res = res * base + x;
        return res;
    }

    mint query(const std::vector<mint>& hash, int l, int r) {
        assert(0 <= l && l <= r);
        extend(r - l);
        return hash[r] - hash[l] * power[r - l];
    }

    mint combine(mint h1, mint h2, int h2_len) {
        extend(h2_len);
        return h1 * power[h2_len] + h2;
    }

    int lcp(const std::vector<mint>& a, int l1, int r1, const std::vector<mint>& b, int l2, int r2) {
        int len = std::min(r1 - l1, r2 - l2);
        int lb = 0, ub = len + 1;
        while (ub - lb > 1) {
            int mid = (lb + ub) >> 1;
            (query(a, l1, l1 + mid) == query(b, l2, l2 + mid) ? lb : ub) = mid;
        }
        return lb;
    }

  private:
    static constexpr unsigned long long mod = hash_impl::mod;
    const mint base = hash_impl::base;
    std::vector<mint> power;

    inline void extend(size_t len) {
        if (power.size() > len) return;
        int pre = power.size();
        power.resize(len + 1);
        for (int i = pre - 1; i < len; i++) power[i + 1] = power[i] * base;
    }
};

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::string S;
    std::cin >> S;

    RollingHash RH;
    auto v = RH.build(S);
    std::map<unsigned long long, int> mp;
    for (size_t j = 1; j <= 10; j++) {
        for (size_t i = 0; i + j <= S.size(); i++) {
            mp[RH.query(v, i, i + j).val()]++;
        }
    }

    int M, ans = 0;
    std::cin >> M;
    for (; M--;) {
        std::string C;
        std::cin >> C;
        ans += mp[RH.get(C).val()];
    }

    std::cout << ans << '\n';
}
0