ciphereck's blog

By ciphereck, history, 6 days ago, In English,

Please can someone help me with the various code implementation of TRIE in C++. I know how trie works, but I want to know how to code Trie ?

 
 
 
 
  • Vote: I like it  
  • -11
  • Vote: I do not like it  

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my implementation: http://www.infoarena.ro/job_detail/1977710?action=view-source You had 4 operations: insert a word, delete a word, find if a word was inserted or find the longest prefix a word has with a word in the trie.

»
6 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Here is my implementation of Trie for pattern searching:

Code
  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain the working of the code ??

»
6 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
class Trie {
private:
   struct Node {
      map<char, Node*> Children;
      bool EndOfWord = false;
      int Counter = 0;
   };

   Node* root;

   void Dfs(Node* current, string s) {
      if (current->EndOfWord == true)
         cout << s << endl;

      for (auto x : current->Children)
         Dfs(x.second, s + x .first);
   }

public:
   Trie() {
      root = new Node();
   }
   
   void Add(string s) {
      Node* current = root;

      for (auto x : s) {
         if (current->Children.count(x) == 0) {
            current->Children[x] = new Node();
         }
         current = current->Children[x];
         current->Counter++;
      }
      current->EndOfWord = true;
   }

   void Traverse() {
      Dfs(root, "");
   }
};
»
5 days ago, # |
Rev. 6   Vote: I like it +1 Vote: I do not like it

you can find implementation of this in codechef:solution of user! you need just search "trie codechef editorial" and have all type of trie for this! even persistence in GDP problem! or in one problem from Zscoder from MCO malasiya have two type of this(one for binary and one for string).... do this !