Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <unordered_map>
- #include <string>
- using namespace std;
- struct TrieNode {
- unordered_map<char, TrieNode*> children;
- int counter;
- TrieNode() : counter(0) {}
- };
- class Trie {
- public:
- Trie() {
- root = new TrieNode();
- }
- void insert(const string& word) {
- TrieNode* node = root;
- node->counter++; // увеличиваем счетчик в корне
- for (char ch : word) {
- if (!node->children.count(ch)) {
- node->children[ch] = new TrieNode();
- }
- node = node->children[ch];
- node->counter++;
- }
- }
- int query(const string& word) {
- TrieNode* node = root;
- int depth = 0;
- for (char ch : word) {
- if (!node->children.count(ch)) {
- break;
- }
- node = node->children[ch];
- ++depth;
- }
- return node->counter + depth;
- }
- private:
- TrieNode* root;
- };
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int n;
- cin >> n;
- Trie trie;
- for (int i = 0; i < n; ++i) {
- string word;
- cin >> word;
- trie.insert(word);
- }
- int q;
- cin >> q;
- while (q--) {
- string query;
- cin >> query;
- cout << trie.query(query) << '\n';
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment
