結果
問題 | No.430 文字列検索 |
ユーザー | ta7uw |
提出日時 | 2019-10-13 11:39:25 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 2,906 bytes |
コンパイル時間 | 1,542 ms |
コンパイル使用メモリ | 182,708 KB |
実行使用メモリ | 27,776 KB |
最終ジャッジ日時 | 2024-11-10 00:35:59 |
合計ジャッジ時間 | 3,030 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 268 ms
27,776 KB |
testcase_02 | AC | 9 ms
5,248 KB |
testcase_03 | AC | 9 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 255 ms
27,520 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 13 ms
5,760 KB |
testcase_11 | AC | 72 ms
8,704 KB |
testcase_12 | AC | 74 ms
8,704 KB |
testcase_13 | AC | 73 ms
8,832 KB |
testcase_14 | AC | 57 ms
7,296 KB |
testcase_15 | AC | 45 ms
6,400 KB |
testcase_16 | AC | 11 ms
5,248 KB |
testcase_17 | AC | 10 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll, ll>; using Graph = vector<vector<ll>>; #define rep(i, n) for(ll i=0;i<(ll)(n);i++) #define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++) #define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--) const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1}; const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1}; const ll MOD = 1000000007; const ll INF = 1000000000000000000L; #ifdef __DEBUG /** * For DEBUG * https://github.com/ta7uw/cpp-pyprint */ #include "cpp-pyprint/pyprint.h" #endif class RollingHash { static const ll base1 = 1009; static const ll base2 = 2009; static const ll mod1 = 1000000007; static const ll mod2 = 1000000009; vector<ll> hash1, hash2, pow1, pow2; public: RollingHash(const string &S) { int n = (int) S.size(); hash1.assign(n + 1, 0); hash2.assign(n + 1, 0); pow1.assign(n + 1, 1); pow2.assign(n + 1, 1); for (int i = 0; i < n; ++i) { hash1[i + 1] = (hash1[i] * base1 + S[i]) % mod1; hash2[i + 1] = (hash2[i] * base2 + S[i]) % mod2; pow1[i + 1] = (pow1[i] * base1) % mod1; pow2[i + 1] = (pow2[i] * base2) % mod2; } } inline pair<ll, ll> get(int l, int r) const { ll res1 = hash1[r] - hash1[l] * pow1[r - l] % mod1; if (res1 < 0) res1 += mod1; ll res2 = hash2[r] - hash2[l] * pow2[r - l] % mod2; if (res2 < 0) res2 += mod2; return {res1, res2}; } inline pair<ll, ll> get(int p) const { ll res1 = hash1[p + 1]; ll res2 = hash2[p + 1]; return {res1, res2}; } inline pair<ll, ll> hash(const string s) const { return get(0, s.size()); } inline int getLCP(int a, int b) const { int len = min((int) hash1.size() - a, (int) hash1.size() - b); int low = 0, high = len; while (high - low > 1) { int mid = (low + high) >> 1; if (get(a, a + mid) != get(b, b + mid)) high = mid; else low = mid; } return low; } }; void Main() { string S; int M; cin >> S >> M; vector<string> C(M); rep(i, M) cin >> C[i]; RollingHash rollingHash(S); map<P, int> target; int N = (int) S.size(); rep(i, N) { rep2(j, 1, 11) { if (i + j <= N) { target[rollingHash.get(i, i + j)]++; } } } int ans = 0; rep(i, M) { string c = C[i]; RollingHash rollingHash1(c); P p = rollingHash1.hash(c); if (target.find(p) != target.end()) { ans += target[p]; } } cout << ans << '\n'; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); Main(); return 0; }