implementation of TRIE / PREFIX TREE .

#include<iostream.h>

#include<conio.h>

#include<string.h>

#include<stdio.h>

#include<process.h>

class node

{

public:

      int prefix_count;

      int is_end;

      node *child[26];

      node()

      {

            prefix_count=0;

            is_end=0;

            for(int i=0;i<26;i++)

                  child[i]=NULL;

      }

}*head;

void insert(char *word)

{

      int len=strlen(word);

      node *current=head;

      current->prefix_count++;

      for(int i=0;i<len;i++)

      {

            int letter = word[i]-(int)'a';

            if(current->child[letter]==NULL)

                  current->child[letter]=new node;

            current->child[letter]->prefix_count++;

            current=current->child[letter];

      }

      current->is_end=1;

}

int search(char *word)

{

      int len=strlen(word);

      node *cur=head;

      for(int i=0;i<len;i++)

      {

            int letter=word[i]-(int)'a';

            if(cur->child[letter]==NULL)

                  return 0;

            cur=cur->child[letter];

      }

      return cur->is_end;

}

int prefix_words(char *pre)

{

      int len=strlen(pre);

      node *cur=head;

      for(int i=0;i<len;i++)

      {

            int letter=pre[i]-(int)'a';

            if(cur->child[letter]==NULL)

                  return 0;

            cur=cur->child[letter];

      }

      return cur->prefix_count;

}

void main()

{

      clrscr();

      int choice;

      char *word;

      cout<<"1.INSERT WORD\n2.SEARCH\n3.NO OF WORDS WITH PREFIX\n4.EXIT";

      while(1)

      {

            cout<<"\nchoice? ";

            cin>>choice;

            switch(choice)

            {

                  case 1:     cout<<"\nWORD TO INSERT : ";

                        gets(word);

                        insert(word);

                        break;

                  case 2:     cout<<"\nWORD TO SEARCH : ";

                        gets(word);

                        int present=search(word);

                        if(present)

                              cout<<"Present";

                        else

                              cout<<"Not Present";

                        break;

                  case 3:     cout<<"\nENTER PREFIX : ";

                        gets(word);

                        int no=prefix_words(word);

                        cout<<no<<" words with "<<word<<" prefix ";

                        break;

                  case 4:     exit(0);

            }

      }

}