結果

問題 No.430 文字列検索
コンテスト
ユーザー kwm_t
提出日時 2026-06-12 10:56:13
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 3,465 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,729 ms
コンパイル使用メモリ 348,748 KB
実行使用メモリ 28,032 KB
最終ジャッジ日時 2026-06-12 10:56:20
合計ジャッジ時間 4,527 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<long long, long long>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_STRING_ROLLING_HASH_HPP
#define KWM_T_STRING_ROLLING_HASH_HPP

#include <vector>
#include <utility>

/**
 * @brief Rolling Hash（静的・ダブルハッシュ）
 *
 * 文字列や配列に対して prefix hash を構築し、
 * 任意区間のハッシュを O(1) で取得できる
 *
 * 計算量:
 *   構築: O(N)
 *   クエリ: O(1)
 *
 * @tparam T 要素型（char, int など）
 *
 * @param s 入力列
 *
 * 使用例:
 *   RollingHash<std::string> rh(s);
 *   auto h = rh.get(l, r); // [l, r)
 *
 *   if (rh.get(l1, r1) == rh.get(l2, r2)) {
 *       // substring equal
 *   }
 *
 * 制約 / 注意:
 *   - 衝突の可能性は低いがゼロではない
 *   - T は整数として扱える必要あり
 *
 * verified:
 *   - substring一致判定
 *   - 回文判定
 */
namespace kwm_t::string {

template <typename Container>
struct RollingHash {
private:
	using ll = long long;

	static constexpr ll base1 = 1007;
	static constexpr ll base2 = 2009;
	static constexpr ll mod1 = 1000000007;
	static constexpr ll mod2 = 1000000009;

	std::vector<ll> hash1, hash2;
	std::vector<ll> power1, power2;

public:
	RollingHash() = default;

	explicit RollingHash(const Container& s) {
		build(s);
	}

	void build(const Container& s) {
		int n = (int)s.size();

		hash1.assign(n + 1, 0);
		hash2.assign(n + 1, 0);
		power1.assign(n + 1, 1);
		power2.assign(n + 1, 1);

		for (int i = 0; i < n; ++i) {
			ll x = (ll)s[i];

			hash1[i + 1] = (hash1[i] * base1 + x) % mod1;
			hash2[i + 1] = (hash2[i] * base2 + x) % mod2;

			power1[i + 1] = (power1[i] * base1) % mod1;
			power2[i + 1] = (power2[i] * base2) % mod2;
		}
	}

	/**
	 * @brief 区間 [l, r) のハッシュを取得
	 */
	std::pair<ll, ll> get(int l, int r) const {
		ll res1 = hash1[r] - hash1[l] * power1[r - l] % mod1;
		if (res1 < 0) res1 += mod1;

		ll res2 = hash2[r] - hash2[l] * power2[r - l] % mod2;
		if (res2 < 0) res2 += mod2;

		return { res1, res2 };
	}

	/**
	 * @brief 長さを取得
	 */
	int size() const {
		return (int)hash1.size() - 1;
	}
};

} // namespace kwm_t::string

#endif // KWM_T_STRING_ROLLING_HASH_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	string s; cin >> s;
	int m; cin >> m;
	kwm_t::string::RollingHash rh(s);
	vector<map<P, int>>mp(11);
	int n = s.size();
	rep2(i, 1, 11) {
		rep(l, n) {
			int r = l + i;
			if (r > n)break;
			mp[i][rh.get(l, r)]++;
		}
	}
	long long ans = 0;
	while (m--) {
		string s; cin >> s;
		kwm_t::string::RollingHash rh(s);
		auto hash = rh.get(0, s.size());
		ans += mp[s.size()][hash];
	}
	cout << ans << endl;
	return 0;
}
0