結果
問題 | No.430 文字列検索 |
ユーザー | yukim0359 |
提出日時 | 2024-06-22 20:01:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,764 ms / 2,000 ms |
コード長 | 1,340 bytes |
コンパイル時間 | 1,685 ms |
コンパイル使用メモリ | 167,820 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-10 01:11:42 |
合計ジャッジ時間 | 13,633 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 374 ms
5,248 KB |
testcase_02 | AC | 787 ms
5,248 KB |
testcase_03 | AC | 546 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 4 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 1,638 ms
5,248 KB |
testcase_12 | AC | 1,663 ms
5,248 KB |
testcase_13 | AC | 1,652 ms
5,248 KB |
testcase_14 | AC | 1,764 ms
5,248 KB |
testcase_15 | AC | 1,550 ms
5,248 KB |
testcase_16 | AC | 882 ms
5,248 KB |
testcase_17 | AC | 817 ms
5,248 KB |
ソースコード
// https://yukicoder.me/problems/no/430 #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #define rep0(i,n) for(int i=0; i<n; ++i) #define rep1(i,n) for(int i=1; i<=n; ++i) void create_table(int *table, string pattern){ int N = pattern.length(); int j = 0; table[j] = 0; rep1(i, N-2){ if(pattern[i] == pattern[j]){ j += 1; table[i] = j; } else{ while( pattern[i] != pattern[j] && j!=0 ){ j = table[j-1]; } if(pattern[i] == pattern[j]) j+=1; table[i] = j; } } } int KMP(string text, string pattern, int *table){ int ans = 0; int t_len = text.length(); int p_len = pattern.length(); int t_i = 0; int p_i = 0; while( t_i<t_len ){ if(text[t_i] == pattern[p_i]){ t_i += 1; p_i += 1; } else if(p_i == 0) t_i += 1; else p_i = table[p_i - 1]; if(p_i == p_len){ ans += 1; p_i = 0; t_i -= (p_len - 1); } } return ans; } int main(){ string S; cin >> S; int M; cin >> M; int ans = 0; rep1(i, M){ string C; cin >> C; if(C.length() != 1){ int table[C.length()-1]; create_table(table, C); ans += KMP(S, C, table); } else{ int table = 1; ans += KMP(S, C, &table); } } cout << ans << endl; }