SHARE
TWEET

Untitled

a guest May 19th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifndef __TRIE_H
  2. #define __TRIE_H
  3.  
  4. #include <cstdio>
  5. #include <iostream>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <string>
  9. #include <stack>
  10.  
  11. int ALPHABET_SIZE = 26;
  12.  
  13. template <typename T>
  14. class Trie
  15. {
  16.  private:
  17.     int count;
  18.     std::vector<Trie<T> *> children;
  19.     T value;
  20.     bool isEndOfWord;
  21.   public:
  22.     Trie() {}
  23.    
  24.     Trie(int capacity, T value)
  25.       : count(0),
  26.         children(capacity, NULL),
  27.         value(value) { }
  28.        
  29.     Trie(int capacity)
  30.       : count(0),
  31.         children(capacity, NULL) { }
  32.        
  33.     ~Trie() {}
  34.     void insert(std::string key, T value) {
  35.         // TODO 1 implementati functia de inserare in Trie
  36.         Trie<T> *currentNode = this;
  37.         for (int i = 0; i < key.size(); ++i) {
  38.             if (currentNode->children[key[i] - 'a'] == NULL) {
  39.                 currentNode->children[key[i] - 'a'] = new Trie<int>(ALPHABET_SIZE);
  40.             }
  41.             currentNode = currentNode->children[key[i] - 'a'];
  42.         }
  43.         currentNode->count++;
  44.         currentNode->value = value;
  45.     }
  46.     bool search(std::string key, T &val) {
  47.         // TODO 1 implementati functia de cautare in Trie
  48.         Trie<T> *currentNode = this;
  49.         for (int i = 0; i < key.size(); ++i) {
  50.             if (currentNode->children[key[i] - 'a'] == NULL) {
  51.                 return false;
  52.             }
  53.             currentNode = currentNode->children[key[i] - 'a'];
  54.         }
  55.         if (currentNode->count == 0) {
  56.             return false;
  57.         }
  58.         val = currentNode->value;
  59.         return true;
  60.     }
  61.    
  62.     bool remove(std::string key) {
  63.         // TODO 2 implementati functia de stergere din Trie
  64.         Trie<T> *currentNode = this;
  65.         for (int i = 0; i < key.size(); ++i) {
  66.             if (currentNode->children[key[i] - 'a'] == NULL) {
  67.                 return false;
  68.             }
  69.             currentNode = currentNode->children[key[i] - 'a'];
  70.         }
  71.         currentNode->count = 0;
  72.         currentNode->value = 0;
  73.         return true;
  74.     }
  75.    
  76.     int numWordsWithPrefix(std::string prefix) {
  77.         // TODO BONUS implementati gasirea numarului de cuvinte din Trie avand prefixul dat
  78.         int ans = 0;
  79.         Trie<T> *currentNode = this;
  80.         for (int i = 0; i < prefix.size(); ++i) {
  81.             if (currentNode->children[prefix[i] - 'a'] == NULL) {
  82.                 return 0;
  83.             }
  84.             currentNode = currentNode->children[prefix[i] - 'a'];
  85.         }
  86.         std::stack<Trie<T>* >stk;
  87.         stk.push(currentNode);
  88.         while(!stk.empty()) {
  89.             currentNode = stk.top();
  90.             stk.pop();
  91.             ans += currentNode->count;
  92.             for (int i = 0; i < ALPHABET_SIZE; ++i) {
  93.                 if (currentNode->children[i] != NULL) {
  94.                     stk.push(currentNode->children[i]);
  95.                 }
  96.             }
  97.         }
  98.         return ans;
  99.     }
  100.  
  101. };
  102. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top