結果
問題 | No.430 文字列検索 |
ユーザー | nawawan |
提出日時 | 2021-09-05 04:54:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 394 ms / 2,000 ms |
コード長 | 2,871 bytes |
コンパイル時間 | 2,341 ms |
コンパイル使用メモリ | 210,648 KB |
実行使用メモリ | 267,280 KB |
最終ジャッジ日時 | 2024-11-10 00:57:25 |
合計ジャッジ時間 | 3,756 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 394 ms
267,280 KB |
testcase_02 | AC | 18 ms
5,504 KB |
testcase_03 | AC | 17 ms
5,632 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 | 381 ms
267,132 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 36 ms
32,772 KB |
testcase_11 | AC | 68 ms
24,292 KB |
testcase_12 | AC | 67 ms
24,300 KB |
testcase_13 | AC | 65 ms
24,404 KB |
testcase_14 | AC | 49 ms
18,820 KB |
testcase_15 | AC | 35 ms
13,300 KB |
testcase_16 | AC | 18 ms
6,268 KB |
testcase_17 | AC | 18 ms
5,760 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<const int char_size> struct Trie_Node{ vector<int> nex, accept; int count; Trie_Node() : count(0){ nex.resize(char_size, -1); } }; template<int char_size, int offset> struct Trie{ private: using Node = Trie_Node<char_size>; vector<Node> Nodes; int root; //文字列の挿入O(|word|) void insert(const string &word, const int str_index){ int now = root; for(int i = 0; i < (int)word.size(); i++){ int id = word[i] - offset; if(Nodes[now].nex[id] == -1){ add(now, id); } ++Nodes[now].count; now = Nodes[now].nex[id]; } ++Nodes[now].count; Nodes[now].accept.push_back(str_index); } void add(int Node_id, int char_id){ Nodes[Node_id].nex[char_id] = (int)Nodes.size(); Nodes.push_back(Node()); } public: Trie() : root(0){ Nodes.push_back(Node()); } void insert(const string &word){ insert(word, Nodes[0].count); } //単語検索O(|word|) int exist(const string &word, bool p = false){ int now = 0; for(int i = 0; i < (int)word.size(); i++){ int temp = word[i] - offset; if(Nodes[now].nex[temp] == -1) return 0; now = Nodes[now].nex[temp]; } if(p) return Nodes[now].count; return (int)Nodes[now].accept.size(); } int prefix(const string &word){ return exist(word, true); } //辞書順に数えてk番目の文字列を出力 O(|word|)(定数倍26)? string kth_string(int k){ assert(k <= count()); string res; int now = 0; int sum = 0; int cnt = 0; while(sum < k){ cnt++; int nxt = -1; for(int i = 0; i < char_size; i++){ int nxt = Nodes[now].nex[i]; if(nxt == -1) continue; int temp = sum + Nodes[nxt].count; if(temp >= k){ res += (char)(offset + i); now = nxt; break; } sum += Nodes[nxt].count; } sum += (int)Nodes[now].accept.size(); } return res; } int count(){ return Nodes[0].count; } int size(){ return (int)Nodes.size(); } }; int main(){ vector<Trie<26, 'A'>> trie(10); string S; cin >> S; int sz = S.size(); for(int i = 1; i <= 10; i++){ for(int j = 0; j + i <= sz; j++){ trie[i - 1].insert(S.substr(j, i)); } } int M; cin >> M; long long sum = 0; for(int i = 0; i < M; i++){ string C; cin >> C; sum += trie[C.size() - 1].prefix(C); } cout << sum << endl; }