結果
問題 | No.430 文字列検索 |
ユーザー | pes_magic |
提出日時 | 2020-08-12 18:56:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 2,412 bytes |
コンパイル時間 | 851 ms |
コンパイル使用メモリ | 85,576 KB |
実行使用メモリ | 10,276 KB |
最終ジャッジ日時 | 2024-11-10 00:45:46 |
合計ジャッジ時間 | 1,594 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 18 ms
10,276 KB |
testcase_02 | AC | 10 ms
7,360 KB |
testcase_03 | AC | 8 ms
6,592 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 | 2 ms
5,248 KB |
testcase_08 | AC | 4 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 3 ms
5,248 KB |
testcase_11 | AC | 13 ms
7,236 KB |
testcase_12 | AC | 12 ms
7,588 KB |
testcase_13 | AC | 13 ms
7,592 KB |
testcase_14 | AC | 12 ms
6,980 KB |
testcase_15 | AC | 11 ms
6,732 KB |
testcase_16 | AC | 12 ms
7,556 KB |
testcase_17 | AC | 11 ms
7,688 KB |
ソースコード
#include <iostream> #include <vector> #include <string> #include <queue> using namespace std; template<int char_size, int base> class PMA { public: explicit PMA(const vector<string>& pattern){ build_(pattern); } vector<vector<int>> match(const string& s) const { vector<vector<int>> res(s.size()); int pos = 0; for(int i=0;i<s.size();i++){ int b = s[i] - base; while(node[pos].next[b] == -1) pos = node[pos].fail; pos = node[pos].next[b]; copy(node[pos].accept.begin(), node[pos].accept.end(), back_inserter(res[i])); } return res; } private: void build_(const vector<string>& pattern){ node.emplace_back(); for(int i=0;i<pattern.size();i++){ int nodeId = 0; for(const auto& c : pattern[i]){ int b = c - base; int& nextId = node[nodeId].next[b]; if(nextId == -1){ nextId = node.size(); node.emplace_back(Node()); } nodeId = nextId; } node[nodeId].accept.push_back(i); } queue<int> qu; for(int i=0;i<char_size;i++){ if(node[0].next[i] == -1){ node[0].next[i] = 0; } else { qu.push(node[0].next[i]); } } while(!qu.empty()){ int cur = qu.front(); qu.pop(); const auto& preAc = node[node[cur].fail].accept; copy(preAc.begin(), preAc.end(), back_inserter(node[cur].accept)); for(int i=0;i<char_size;i++){ int next = node[cur].next[i]; if(next == -1) continue; int nxt = node[cur].fail; while(node[nxt].next[i] == -1) nxt = node[nxt].fail; node[node[cur].next[i]].fail = node[nxt].next[i]; qu.push(node[cur].next[i]); } } } private: struct Node { vector<int> next; vector<int> accept; int fail; Node() : next(char_size, -1), fail(0) {} }; vector<Node> node; }; int main(){ string S; cin >> S; int M; cin >> M; vector<string> C(M); for(auto& c : C) cin >> c; PMA<26, 'A'> pma(C); auto m = pma.match(S); int res = 0; for(auto& v : m) res += v.size(); cout << res << endl; }