Introduction to competitive programming

Trie Data Structure Implementation

Trie can insert and search string in O(L) time where L is the length of string,this is much faster than hashtable and binary search tree implementations. Trie Node consist of a collection of Trie nodes and a boolean flag to check whether node is leaf or not.

Tutorial Links

Tutorial Link

Also Topcoder had excellent explanation about TRIE

Here is the C++ implementation of above Algorithm

/*
  TRIE implementation in C++
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ALPHABET_SIZE 26
using namespace std;
struct Node
{
 struct Node *child[ALPHABET_SIZE];
 bool isLeaf;
};
struct Node *createNode()
{
 Node *nw=new Node;
 for(int i=0;i<26;i++)
  nw->child[i]=NULL;
 nw->isLeaf=0;
 return nw;
}
void addWord(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
  {
   temp->child[c]=createNode();
  }
  temp=temp->child[c];
 }
 temp->isLeaf=1;
}
bool search(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
   return false;
  temp=temp->child[c];
 }
 if(temp->isLeaf)
  return true;
 else
  return false;
}
void printAllStrings(struct Node *root,string s)
{
 if(!root)
  return;
 if(root->isLeaf)
 {
  cout<<s<<"\n";
  return;
 }
 else
 {
  for(int i=0;i<26;i++)
  {
   if(root->child[i])
   {
 
    printAllStrings(root->child[i],s+(char)('a'+i));
   }
  }
 }
}
int main()
{
 struct Node *root=createNode();
 addWord(root,"abcd");
 addWord(root,"ace");
 if(search(root,"sai"))
  cout<<"Sai found\n";
 else
  cout<<"Sai not found\n";
 if(search(root,"abcd"))
  cout<<"abcd found\n";
 else
  cout<<"abcd not found\n";
 printAllStrings(root,"");
}