This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <cassert> #include <functional> using namespace std; #include "../str_004_trie.cpp" void tiny_test() { trie<26, 'a'> tr; int N; cin >> N; for(int i=0; i<N; i++) { string s; cin >> s; tr.add(s); } int K; while(cin >> K) { cout << tr.kth_string(K) << endl; } } int main() { tiny_test(); }
#line 1 "string/verify/verify_str_004_trie.cpp" #include <iostream> #include <string> #include <algorithm> #include <vector> #include <cassert> #include <functional> using namespace std; #line 1 "string/str_004_trie.cpp" // トライ木 // Vefiried: 天下一プログラマーコンテスト 2016 本戦 C: たんごたくさん template <int char_size> struct trie_node { int nxt_node[char_size]; size_t child; vector<int> accept; trie_node() : child(0), accept() { fill(nxt_node, nxt_node + char_size, -1); } size_t size() const { return child + accept.size(); } }; template <int char_size, int margin> struct trie { using node = trie_node<char_size>; vector<node> nodes; int root; void terminate(int node_idx, int id) { nodes[node_idx].accept.emplace_back(id); } void add(const string &s, int node_idx, size_t str_idx, int id) { if(str_idx == s.size()) { terminate(node_idx, id); } else { nodes[node_idx].child++; const int c = s[str_idx] - margin; if(nodes[node_idx].nxt_node[c] == -1) { nodes[node_idx].nxt_node[c] = nodes.size(); nodes.emplace_back(node()); } add(s, nodes[node_idx].nxt_node[c], str_idx + 1, id); } } void query(const string &s, function< void(int) > &f, int node_idx, int str_idx, bool only_complete_match) { if(str_idx == s.size() or !only_complete_match) { for(auto k : nodes[node_idx].accept) f(k); } if(str_idx == s.size()) return; const int c = s[str_idx] - margin; if(nodes[node_idx].nxt[c] == -1) return; query(s, f, nodes[node_idx].nxt[c], str_idx + 1, only_complete_match); } trie() : root(0) { nodes.emplace_back(node()); } // 文字列の追加 O(|S|) // 重複による特別扱いはしないので、複数回入れたら複数回反映される void add(const string &s, int id) { add(s, root, 0, id); } void add(const string &s) { add(s, nodes[root].child); } // 1-indexed, O(k 番目の文字列の長さ * \sigma) くらい string kth_string(size_t k) { assert(1 <= k and k <= nodes[root].child); int node_idx = root; string res = ""; while(k > 0) { if(k <= nodes[node_idx].accept.size()) break; k -= nodes[node_idx].accept.size(); for(size_t i=0; i<char_size; i++) { int c = nodes[node_idx].nxt_node[i]; if(c < 0) continue; if(nodes[c].size() >= k) { res += (char)(margin + i); node_idx = c; break; } else { k -= nodes[c].size(); } } } return res; } // 文字列 s の prefix に match する文字列それぞれについて、何か作用させる // 完全一致しか許さない場合は true も引数に与える void query(const string &s, const function< void(int) > &f, bool only_complete_match = false) { query(s, f, 0, 0, only_complete_match); } // 登録されている文字列がいくつか size_t count() const { return nodes[root].child; } // ノード数 size_t size() const { return nodes.size(); } }; #line 9 "string/verify/verify_str_004_trie.cpp" void tiny_test() { trie<26, 'a'> tr; int N; cin >> N; for(int i=0; i<N; i++) { string s; cin >> s; tr.add(s); } int K; while(cin >> K) { cout << tr.kth_string(K) << endl; } } int main() { tiny_test(); }