結果
問題 | No.430 文字列検索 |
ユーザー | KowerKoint2010 |
提出日時 | 2022-04-27 00:01:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,743 ms / 2,000 ms |
コード長 | 5,814 bytes |
コンパイル時間 | 2,019 ms |
コンパイル使用メモリ | 209,712 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-10 01:00:13 |
合計ジャッジ時間 | 14,995 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 622 ms
5,248 KB |
testcase_02 | AC | 881 ms
5,248 KB |
testcase_03 | AC | 760 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 4 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 3 ms
5,248 KB |
testcase_11 | AC | 1,742 ms
5,248 KB |
testcase_12 | AC | 1,739 ms
5,248 KB |
testcase_13 | AC | 1,743 ms
5,248 KB |
testcase_14 | AC | 1,708 ms
5,248 KB |
testcase_15 | AC | 1,522 ms
5,248 KB |
testcase_16 | AC | 946 ms
5,248 KB |
testcase_17 | AC | 885 ms
5,248 KB |
ソースコード
#line 2 "library/KowerKoint/base.hpp" #ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++) #define ALL(a) (a).begin(),(a).end() #define END(...) { print(__VA_ARGS__); return; } using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>; using ll = long long; using VL = vector<ll>; using VVL = vector<VL>; using VVVL = vector<VVL>; using VD = vector<double>; using VVD = vector<VD>; using VVVD = vector<VVD>; using VS = vector<string>; using VVS = vector<VS>; using VVVS = vector<VVS>; using VC = vector<char>; using VVC = vector<VC>; using VVVC = vector<VVC>; using P = pair<int, int>; using VP = vector<P>; using VVP = vector<VP>; using VVVP = vector<VVP>; using LP = pair<ll, ll>; using VLP = vector<LP>; using VVLP = vector<VLP>; using VVVLP = vector<VVLP>; template <typename T> using PQ = priority_queue<T>; template <typename T> using GPQ = priority_queue<T, vector<T>, greater<T>>; constexpr int INF = 1001001001; constexpr ll LINF = 1001001001001001001ll; constexpr int DX[] = {1, 0, -1, 0}; constexpr int DY[] = {0, 1, 0, -1}; void print() { cout << '\n'; } template<typename T> void print(const T &t) { cout << t << '\n'; } template<typename Head, typename... Tail> void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } #ifdef ONLINE_JUDGE template<typename... Args> void dbg(const Args &... args) {} #else void dbg() { cerr << '\n'; } template<typename T> void dbg(const T &t) { cerr << t << '\n'; } template<typename Head, typename... Tail> void dbg(const Head &head, const Tail &... tail) { cerr << head << ' '; dbg(tail...); } #endif template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != (int) v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template<typename T> vector<vector<T>> split(typename vector<T>::const_iterator begin, typename vector<T>::const_iterator end, T val) { vector<vector<T>> res; vector<T> cur; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(val); } res.push_back(cur); return res; } vector<string> split(typename string::const_iterator begin, typename string::const_iterator end, char val) { vector<string> res; string cur = ""; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(val); } res.push_back(cur); return res; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template <typename T> pair<VI, vector<T>> compress(const vector<T> &a) { int n = a.size(); vector<T> x; REP(i, n) x.push_back(a[i]); sort(ALL(x)); x.erase(unique(ALL(x)), x.end()); VI res(n); REP(i, n) res[i] = lower_bound(ALL(x), a[i]) - x.begin(); return make_pair(res, x); } template <typename T> pair<vector<T>, vector<T>> factorial(int n) { vector<T> res(n+1), rev(n+1); res[0] = 1; REP(i, n) res[i+1] = res[i] * (i+1); rev[n] = 1 / res[n]; for(int i = n; i > 0; i--) { rev[i-1] = rev[i] * i; } return make_pair(res, rev); } #line 2 "library/KowerKoint/test/yukicoder-430/main.cpp" /* #include <atcoder/all> */ /* using namespace atcoder; */ /* #include "KowerKoint/expansion/ac-library/all.hpp" */ #line 2 "library/KowerKoint/string.hpp" #line 4 "library/KowerKoint/string.hpp" template <typename It> vector<int> kmp_table(It begin, It end) { int m = end - begin; vector<int> table(m); int j = 0; FOR(i, 1, m) { while(j > 0 && *(begin+i) != *(begin+j)) j = table[j-1]; if(*(begin+i) == *(begin+j)) table[i] = ++j; } return table; } template <typename It> vector<int> kmp_find(It s_begin, It s_end, It t_begin, It t_end, vector<int>& table) { typename iterator_traits<It>::value_type T; int n = s_end - s_begin; int m = t_end - t_begin; vector<int> res; int j = 0; REP(i, n) { while(j > 0 && *(s_begin+i) != *(t_begin+j)) j = table[j-1]; if(*(s_begin+i) == *(t_begin+j)) { if(++j == m) { res.push_back(i - (m-1)); j = table[m-1]; } } } return res; } #line 7 "library/KowerKoint/test/yukicoder-430/main.cpp" void solve(){ string s; cin >> s; int m; cin >> m; int ans = 0; REP(i, m) { string c; cin >> c; auto table = kmp_table(ALL(c)); ans += kmp_find(ALL(s), ALL(c), table).size(); } print(ans); } // generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator) int main() { // Fasterize input/output script ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(100); // scanf/printf user should delete this fasterize input/output script int t = 1; //cin >> t; // comment out if solving multi testcase for(int testCase = 1;testCase <= t;++testCase){ solve(); } return 0; }