結果

問題 No.430 文字列検索
コンテスト
ユーザー AC2K
提出日時 2023-03-29 13:24:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 264 ms / 2,000 ms
コード長 3,921 bytes
コンパイル時間 2,676 ms
コンパイル使用メモリ 262,004 KB
実行使用メモリ 27,264 KB
最終ジャッジ日時 2024-11-10 01:05:51
合計ジャッジ時間 4,173 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define rep(i, N)  for(int i=0;i<(N);i++)
#define all(x) (x).begin(),(x).end()
#define popcount(x) __builtin_popcount(x)
using i128=__int128_t;
using ll = long long;
using ld = long double;
using graph = vector<vector<int>>;
using P = pair<int, int>;
constexpr int inf = 1e9;
constexpr ll infl = 1e18;
constexpr ld eps = 1e-6;
const long double pi = acos(-1);
constexpr uint64_t MOD = 1e9 + 7;
constexpr uint64_t MOD2 = 998244353;
constexpr int dx[] = { 1,0,-1,0 };
constexpr int dy[] = { 0,1,0,-1 };
template<class T>static constexpr inline void chmax(T&x,T y){if(x<y)x=y;}
template<class T>static constexpr inline void chmin(T&x,T y){if(x>y)x=y;}
#line 2 "math/mod_pow.hpp"
template <class T, class U = T>
U mod_pow(T base, T exp, T mod){
    T ans = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            ans *= base;
            ans %= mod;
        }
        base *= base;
        base %= mod;
        exp >>= 1;
    }
    return ans;
}
///@brief mod pow(バイナリ法)
#line 3 "string/rolling_hash.hpp"
class RollingHash {
	using ull = uint_fast64_t;
    using i128 = __int128_t;
    using u128 = __uint128_t;
    // mod
	static constexpr ull msk30 = (1ul << 30) - 1;
	static constexpr ull msk61 = (1ul << 31) - 1;
	string str;
	vector<ull> hash, pow;

    static constexpr ull mod = (1uL << 61) - 1;
    static constexpr ull primitive_root = 37;
public:
	static const uint mapping_max = (uint)'Z' + 2;
	static ull base;
private:
	ull mul(const u128& a,const u128& b) const {
        u128 t = a * b;

		t = (t >> 61) + (t & mod);

		if (t >= mod) {
			t -= mod;
		}


		return t;
    }

    ull mapping(const char& c) const {
		return (ull)c;	//変更する?
	}


    static ull generate() {
		mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());
		uniform_int_distribution<ull> rand(1uL, mod - 1);
		return rand(engine);
	}	
    static void generate_base() {
		if (base != 0){
			return;
		}
		ull r = mod - 1;

		while (gcd(r, mod - 1) != 1 || r <= mapping_max){
			r = generate();
		}
		base = mod_pow<__uint128_t>(primitive_root, r, mod);
	}
public:
	RollingHash() :str() {	}

	RollingHash(const string& str) :str(str) {
		generate_base();
		build();
	}

	void build() {
		hash.resize(str.size() + 1);
		pow.resize(str.size() + 1, 1);

		for (int i = 0; i < str.size(); i++) {
			hash[i + 1] = mul(hash[i], base) + mapping(str[i]);
			pow[i + 1] = mul(pow[i], base);
			if (hash[i + 1] >= mod) {
				hash[i + 1] -= mod;
			}
		}
	}
	ull range(int l, int r) const {
		ull res = mod + hash[r] - mul(hash[l], pow[r - l]);
		return res < mod ? res : res - mod;
	}
	ull get_all() const {
		return hash.back();
	}
	int size() const {return str.size();}

    static int lcp(const RollingHash &a, const RollingHash &b, const int &start_a, const int &start_b) {
        int ok = 0;
        int ng = min(a.size() - start_a, b.size() - start_b) + 1;
		while (abs(ok - ng) > 1){
			int md = (ok + ng) >> 1;
            if (a.range(start_a, start_a + md) == b.range(start_b, start_b + md)){
                ok = md;
            }
            else{
                ng = md;
            }
		}

		return ok;
    }
};
typename RollingHash::ull RollingHash::base;

///@brief Rollinghash(ローリングハッシュ)
#line 3 "main.cpp"

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
int main(){
    string s;
    int m;
    cin >> s >> m;
    RollingHash S(s);
    map<uint64_t, int> hash_count;
    rep(i, s.size()) {
        for (int length = 1; length <= 10 && i + length <= s.size(); length++) {
            int j = i + length;
            hash_count[S.range(i, j)]++;
        }
    }
    long long ans = 0;

    for (int i = 0; i < m; i++) {
        string c;
        cin >> c;
        ans += hash_count[RollingHash(c).get_all()];
    }
    cout << ans << '\n';
}
0