結果
問題 | No.430 文字列検索 |
ユーザー | okina25 |
提出日時 | 2023-09-04 17:22:26 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,502 bytes |
コンパイル時間 | 1,545 ms |
コンパイル使用メモリ | 167,852 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-04 17:22:45 |
合計ジャッジ時間 | 17,781 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 991 ms
4,376 KB |
testcase_02 | AC | 941 ms
4,376 KB |
testcase_03 | AC | 822 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 6 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 4 ms
4,380 KB |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | AC | 1,872 ms
4,380 KB |
testcase_16 | AC | 1,056 ms
4,376 KB |
testcase_17 | AC | 979 ms
4,380 KB |
ソースコード
#line 1 "test.cpp" #include <bits/stdc++.h> #line 2 "/Library/kyopro-lib/lib/string/kmp.hpp" /** * @file manachar.hpp * @brief KMPアルゴリズムに関するコード。 * @details * * 文字列SとパターンPに対し、Pの出現位置をO(|P| + |S|)で列挙する。 */ #line 12 "/Library/kyopro-lib/lib/string/kmp.hpp" #line 14 "/Library/kyopro-lib/lib/string/kmp.hpp" using namespace std; // 参考:アルゴリズムイントロダクション第3版 namespace kmp_inner { std::vector<int> compute_prefix_function_(const std::string &P) { const int m = P.size(); std::vector<int> pi(m); pi[0] = -1; int k = -1; for (int q = 1; q < m; ++q) { while (k >= 0 && P[k + 1] != P[q]) { k = pi[k]; } if (P[k + 1] == P[q]) ++k; pi[q] = k; } return pi; } } // namespace kmp_inner std::vector<int> kmp(const std::string &S, const std::string &P) { const int n = S.size(); const int m = P.size(); auto pi = kmp_inner::compute_prefix_function_(P); int q = -1; std::vector<int> ret; for (int i = 0; i < n; ++i) { while (q >= 0 && P[q + 1] != S[i]) q = pi[q]; if (P[q + 1] == S[i]) ++q; if (q == m - 1) { ret.push_back(i - m + 1); q = pi[q]; } } return ret; } #line 4 "test.cpp" using namespace std; int main() { string S; int M; cin >> S >> M; int ans = 0; for (int i = 0; i < M; ++i) { string c; cin >> c; ans += kmp(S, c).size(); } cout << ans << endl; }