結果

問題 No.430 文字列検索
ユーザー DaylightDaylight
提出日時 2022-06-30 17:20:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 411 ms / 2,000 ms
コード長 3,821 bytes
コンパイル時間 2,592 ms
コンパイル使用メモリ 216,120 KB
実行使用メモリ 27,892 KB
最終ジャッジ日時 2024-05-03 13:51:53
合計ジャッジ時間 4,809 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 411 ms
27,892 KB
testcase_02 AC 12 ms
5,848 KB
testcase_03 AC 13 ms
5,848 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 405 ms
27,632 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 16 ms
5,888 KB
testcase_11 AC 97 ms
8,816 KB
testcase_12 AC 99 ms
8,812 KB
testcase_13 AC 99 ms
8,816 KB
testcase_14 AC 75 ms
7,280 KB
testcase_15 AC 56 ms
6,384 KB
testcase_16 AC 19 ms
5,844 KB
testcase_17 AC 16 ms
5,844 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define SZ(x) (int)(x).size()
#define REP(i, n) for(int i=0;i<(n);i++)
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REPR(i, n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , (v).end())

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 29);
const ll LINF = 1e18;
const double PI = acos(-1);

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}

template<class T>
bool chmax(T& a, const T& b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template<class T>
bool chmin(T& a, const T& b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template<typename S, typename T>
istream& operator>>(istream& is, pair<S, T>& p) {
	cin >> p.first >> p.second;
	return is;
}

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i, SZ(vec)) {
		if (i != 0)os << " ";
		os << vec[i];
	}
	return os;
}

struct RollingHash {
	static const uint64_t mod = (1ull << 61ull) - 1;
	using uint128_t = __uint128_t;
	using hash_type = pair<uint64_t,uint64_t>;
	uint64_t base1, base2;
	vector<uint64_t> pow1, pow2;

	RollingHash() {
		mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
		uniform_int_distribution< uint64_t > rand(1e9, RollingHash::mod - 1);
		base1 = rand(mt);
		base2 = rand(mt);
		pow1.push_back(1);
		pow2.push_back(1);
	}

	// 必要分のpow配列を追加で求める。
	inline void expand(int sz) {
		int pre_sz = SZ(pow1);
		if (pre_sz < sz + 1) {
			for (int i = pre_sz - 1; i < sz; i++) {
				pow1.push_back(mul(pow1[i], base1));
				pow2.push_back(mul(pow2[i], base2));
			}
		}
	}
	pair<vector<uint64_t>, vector<uint64_t>> build(const string& s) {
		expand(SZ(s) + 1);
		vector<uint64_t> hash1 = vector<uint64_t>(SZ(s) + 1);
		vector<uint64_t> hash2 = vector<uint64_t>(SZ(s) + 1);
		REP(i, SZ(s)) {
			hash1[i + 1] = add(mul(hash1[i], base1), s[i]);
			hash2[i + 1] = add(mul(hash2[i], base2), s[i]);
		}
		return { hash1,hash2 };
	}

	hash_type query(const pair<vector<uint64_t>, vector<uint64_t>>& hash, int begin, int length) {
		assert(begin + length <= SZ(hash.first));
		assert(begin >= 0);
		assert(length > 0);
		expand(length);
		return { add(hash.first[begin + length], mod - mul(hash.first[begin], pow1[length])),add(hash.second[begin + length], mod - mul(hash.second[begin], pow2[length])) };
	}

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

	static inline uint64_t  mul(uint64_t a, uint64_t b) {
		uint128_t c = (uint128_t)a * b;
		return add(c >> 61, c & mod);
	}
};

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	map<RollingHash::hash_type,ll> m;
	RollingHash rh;
	auto h = rh.build(S);
	REP(i,SZ(S)){
		FOR(j,1,11){
			if(i + j - 1 >= SZ(S))continue;
			m[rh.query(h,i,j)]++;
		}
	}
	int M;
	cin >> M;
	ll ans = 0;
	REP(i,M){
		string c;
		cin >> c;
		auto hc = rh.build(c);
		ans += m[rh.query(hc,0,SZ(c))];
	}
	cout << ans << endl;
	return 0;
}
0