結果
問題 | No.430 文字列検索 |
ユーザー | kkktym |
提出日時 | 2019-09-19 23:53:05 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,428 bytes |
コンパイル時間 | 544 ms |
コンパイル使用メモリ | 67,092 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-21 16:42:35 |
合計ジャッジ時間 | 11,429 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 318 ms
6,940 KB |
testcase_02 | AC | 638 ms
6,940 KB |
testcase_03 | AC | 566 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 4 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,948 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #define rep(i,n) for(int i=0;i<n;++i) #define rep1(i,n) for(int i=1;i<=n;++i) using namespace std; struct STR { string s; int sl; vector<int> table; STR(string _s) { s = _s; sl = s.size(); } void kmp_table(string t) { int tl = t.size(); table.resize(tl+1); table[0] = -1; int i = 1; int j = 0; int cnt = 0; while(1){ while(t[i]==t[j]){ cnt++; table[i] = ((t[0]==t[i])?-1:0); ++i; if(i == tl){ table[i] = cnt; break; } ++j; } if(i == tl){ break; } table[i] = ((t[0]==t[i])?-1:cnt); cnt = 0; ++i; if(i == tl){ table[i] = cnt; break; } j = 0; } } int kmp(string t) { int tl = t.size(); if(tl > sl) return 0; kmp_table(t); int cnt = 0; int i = 0; int j = 0; while(1){ while(s[i] == t[j]){ ++j; if(j==tl){ ++cnt; j = table[j]; } ++i; if(i == sl){ return cnt; } } if(table[j] == -1){ ++i; if(i == sl){ return cnt; } j = 0; } else{ j = table[j]; } } return cnt; } }; int main() { string s; cin >> s; int m; cin >> m; vector<string> t(m); rep(i,m) cin >> t[i]; STR st(s); int res = 0; rep(i,m){ res += st.kmp(t[i]); // cout << st.kmp(t[i]) << "\n"; } cout << res << "\n"; return 0; }