Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

ciphereck's blog

By ciphereck, history, 3 years 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

»
3 years 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.

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

Here is my implementation of Trie for pattern searching:

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

    Can you please explain the working of the code ??

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry, but Could you tell me the meaning of trie[node][s[i]-'a'] please ?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    shouldn't it be finish[node-1]=1 instead of finish[nxt-1]=1 in function Add??

    • »
      »
      »
      9 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      finish[node]=1 is right. Actually his finish[nxt-1]=1 is not correct because it will ignore the case Assume input 2 aabcd aab

      His program will only show that string aabcd is present in trie while string aab is not.

»
3 years 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, "");
   }
};
»
3 years 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 !

»
2 years ago, # |
  Vote: I like it -21 Vote: I do not like it

I downvote!!!