結果
問題 | No.430 文字列検索 |
ユーザー | yuppe19 😺 |
提出日時 | 2016-10-03 11:55:17 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 276 ms / 2,000 ms |
コード長 | 2,750 bytes |
コンパイル時間 | 1,120 ms |
コンパイル使用メモリ | 90,724 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-11-10 00:08:16 |
合計ジャッジ時間 | 4,101 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 265 ms
9,600 KB |
testcase_02 | AC | 263 ms
9,600 KB |
testcase_03 | AC | 264 ms
9,600 KB |
testcase_04 | AC | 3 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 3 ms
5,248 KB |
testcase_08 | AC | 19 ms
9,600 KB |
testcase_09 | AC | 3 ms
5,248 KB |
testcase_10 | AC | 4 ms
5,248 KB |
testcase_11 | AC | 263 ms
9,728 KB |
testcase_12 | AC | 265 ms
9,600 KB |
testcase_13 | AC | 264 ms
9,728 KB |
testcase_14 | AC | 262 ms
9,728 KB |
testcase_15 | AC | 276 ms
9,600 KB |
testcase_16 | AC | 265 ms
9,600 KB |
testcase_17 | AC | 261 ms
9,728 KB |
ソースコード
#include <iostream> #include <algorithm> #include <chrono> #include <random> using namespace std; using i64 = long long; struct rolling_hash { rolling_hash(const string& s, const vector<i64>& mods, const vector<i64>& bases); i64 calc_hash(int l, int r); // [l, r]。つまりlもrも含む。1-indexed private: string s; vector<i64> b[2], H[2]; vector<i64> mods, bases; }; template <class Int> vector<Int> segment_sieve(Int a, Int b) { Int sqb = sqrt(b); vector<bool> is_prime_small(sqb+1, true); is_prime_small[0] = is_prime_small[1] = false; vector<bool> is_prime(b-a, true); is_prime[0] = a != 1; for(Int i=2; i*i<b; ++i) { if(is_prime_small[i]) { for(Int j=2*i; j*j<b; j+=i) { is_prime_small[j] = 0; } for(Int j=max(Int(2), (a+i-1)/i)*i; j<b; j+=i) { is_prime[j - a] = false; } } } vector<Int> res; for(int i=0; i<b-a; ++i) { if(is_prime[i]) { res.push_back(i+a); } } return res; } rolling_hash::rolling_hash(const string& s, const vector<i64>& mods, const vector<i64>& bases) : s(s), mods(mods), bases(bases) { int n = s.size(); i64 B; for(int j=0; j<2; ++j) { B = bases[j] % mods[j]; b[j].resize(n+1); H[j].resize(n+1); b[j][0] = 1; H[j][0] = 0; for(int i=0; i<n; ++i) { b[j][i+1] = b[j][i] * B; b[j][i+1] %= mods[j]; H[j][i+1] = H[j][i] * B + s[i]; H[j][i+1] %= mods[j]; } } } i64 rolling_hash::calc_hash(int l, int r) { i64 h0 = (H[0][r] - b[0][r-l+1] * H[0][l-1]) % mods[0]; if(h0 < 0) { h0 += mods[0]; } i64 h1 = (H[1][r] - b[1][r-l+1] * H[1][l-1]) % mods[1]; if(h1 < 0) { h1 += mods[1]; } i64 hash = (h0 << 31) + h1; return hash; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); mt19937_64 genrand(seed); constexpr i64 LO = i64(powl(2, 30)), HI = LO + 100000; vector<i64> primes = segment_sieve(LO, HI); shuffle(begin(primes), end(primes), genrand); vector<i64> mods, bases; for(int i=0; i<2; ++i) { mods.push_back(primes[i]); bases.push_back(genrand()); } string s; cin >> s; rolling_hash rhs(s, mods, bases); int n = s.size(); vector<vector<i64>> cache(11, vector<i64>(n, 0)); for(int len=1; len<=10; ++len) { for(int start=0; start+len<=n; ++start) { cache[len][start] = rhs.calc_hash(start+1, start+len); } } int M; cin >> M; int res = 0; string t; for(int i=0; i<M; ++i) { cin >> t; int m = t.size(); rolling_hash rht(t, mods, bases); i64 hasht = rht.calc_hash(1, m); for(int start=0; start<n; ++start) { if(cache[m][start] == hasht) { ++res; } } } cout << res << '\n'; return 0; }