結果

問題 No.430 文字列検索
ユーザー DaylightDaylight
提出日時 2023-01-08 15:28:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 443 ms / 2,000 ms
コード長 4,636 bytes
コンパイル時間 2,606 ms
コンパイル使用メモリ 219,084 KB
実行使用メモリ 27,996 KB
最終ジャッジ日時 2024-05-09 07:34:22
合計ジャッジ時間 5,190 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 443 ms
27,996 KB
testcase_02 AC 13 ms
5,464 KB
testcase_03 AC 13 ms
5,376 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 422 ms
27,740 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 19 ms
6,016 KB
testcase_11 AC 104 ms
9,044 KB
testcase_12 AC 105 ms
9,052 KB
testcase_13 AC 107 ms
9,048 KB
testcase_14 AC 75 ms
7,380 KB
testcase_15 AC 56 ms
6,488 KB
testcase_16 AC 17 ms
5,468 KB
testcase_17 AC 15 ms
5,376 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(auto i = (a); i < (b); i++)
#define For(i, a, b, c) \
	for(auto i = (a); i != (b); i += (c))
#define REPR(i, n) for(auto 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())
#define eb emplace_back

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;
typedef vector<vll> vvll;
typedef pair<int, int> PI;
typedef pair<ll, ll> PL;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 30);
const ll LINF = 1e18;
const double math_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>
string join(vector<T>& vec, string splitter) {
	stringstream ss;
	REP(i, SZ(vec)) {
		if(i != 0) ss << splitter;
		ss << vec[i];
	}
	return ss.str();
}

template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	os << join(vec, " ");
	return os;
}
struct RollingHash {
private:
	static const uint64_t mod = (1ull << 61ull) - 1;
	using uint128_t = __uint128_t;
	static inline uint64_t base1 = 0, base2 = 0;
	static inline vector<uint64_t> pow1, pow2;
	vector<uint64_t> hash1, hash2;

	// 必要分の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));
			}
		}
	}
	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);
	}

public:
	/// @brief 指定した文字列に対して,ハッシュを前計算する
	/// @param s ハッシュを取る文字列
	RollingHash(const string& s)
		: RollingHash(vector<char>(s.begin(), s.end())) {
	}

	/// @brief 指定した配列に対して,ハッシュを前計算する
	/// @param s ハッシュを取る配列
	template<typename T>
	RollingHash(const vector<T>& s) {
		if(base1 == 0) {
			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);
		expand(SZ(s) + 1);
		hash1 = vector<uint64_t>(SZ(s) + 1);
		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]);
		}
	}

	/// @brief build関数で計算されたhash値をもとにbegin文字目からlength文字のhash値を求める
	/// @param begin 文字列の初期位置(0-indexed)
	/// @param length 文字列の長さ
	/// @return 2通りのhash値
	pair<uint64_t, uint64_t> query(int begin, int length) {
		assert(begin + length <= SZ(hash1));
		assert(begin >= 0);
		assert(length > 0);
		expand(length);
		return {
			add(hash1[begin + length],
				mod - mul(hash1[begin], pow1[length])),
			add(hash2[begin + length],
				mod - mul(hash2[begin], pow2[length]))
		};
	}
};

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	RollingHash HS(S);
	map<pair<llu, llu>, int> m;
	REP(i, SZ(S)) {
		FOR(len, 1, 11) {
			if(i + len > SZ(S)) break;
			m[HS.query(i, len)]++;
		}
	}
	int M;
	cin >> M;
	int ans = 0;
	REP(i, M) {
		string C;
		cin >> C;
		RollingHash HC(C);
		ans += m[HC.query(0, SZ(C))];
	}
	cout << ans << endl;
	return 0;
}
0