Friday, July 5, 2013

Tries-String Storing and matching Program Using C language.

//A simple Tries implementation in C language, for alphabets.This program can store very efficiently strings and can be further used to find whether it exist or not.

#include<stdio.h>
#include<stdlib.h>
typedef struct TrieNode
{
char data;
int eos;
struct TrieNode *child[26];
}Trie;
Trie *Insertion(Trie *Root,char word[])
{
if(!word)
return Root;
 if(!Root)
 {
  Trie *newnode=(Trie*)malloc(sizeof(Trie));
  newnode->data=*word;
  newnode->eos=1;
  int i=0;
  for(i=0;i<26;i++)
  newnode->child[i]=NULL;


  if(*(word+1)<32)
   newnode->eos=0;
else
newnode->child[*(word+1)-97]=Insertion( newnode->child[*(word+1)-97],word+1);
   return newnode;
 }
  if(*(word+1)<32)
  Root->eos=0;
  else
  Root->child[*(word+1)-97]=Insertion(Root->child[*(word+1)-97],word+1);
 
return Root;
}

int Search(Trie *Root,char word[])
{   if(!Root) return -1;
    if(!word) return -1;
    if(!*word)return -1;

if(Root->data==*word)
{
  printf("%c  %s\n",Root->data,word);
 if(Root->eos==0&& *(word+1)<32)
   {
   return 1;
   }
  else if(*(word+1)<32)
  {
  return -1;
  }
  else
 return Search(Root->child[*(word+1)-97],word+1);
    }
    else
     {
return -1;
     }
}


int main(void)
{
Trie *Root=(Trie*)malloc(sizeof(Trie));
char Text[10];
char Pattern[10];
int i=0;

for(i=0;i<26;i++)
Root->child[i]=NULL;
printf("Enter the text\n");
int j=0;
for(i=0;i<3;i++)
{
j=0;
scanf("%s",Text);
for(j=0;Text[j];j++)  // capital and small letter conversion into capital or invalid results
{
if(Text[j]<97||Text[j]>122)
 {
  if((Text[j]+32)>122||(Text[j]+32)<97)
  {
    printf("Invalid String Try again only Alphabet are allowed\n");
  break;
  }
  else
   {
   Text[j]=Text[j]+32;
        Root->child[*Text-97]=Insertion(Root->child[*Text-97],Text);
        }
      }
      else
      Root->child[*Text-97]=Insertion(Root->child[*Text-97],Text);
}
}

printf("\nEnter the searching word\n");
scanf("%s",Pattern);
for(j=0;Pattern[j];j++)
{
if(Pattern[j]<97)
Pattern[j]=Pattern[j]+32;
}
int k;
k=Search(Root->child[*Pattern-97],Pattern);
if(k==1)printf("\nExist");
else
printf("\nno such word exist");
return 0;
}


No comments:

Post a Comment