Tries and Suffix Trees implementation

Question

I have studied Tries and Suffix Trees and wanted to implement the same. Please share some links where in I can get an idea about the structure and basic idea of implementation to start with.

Any good example, if included, would be a plus.

Implementation in C.

Solution 1

The C Algorithms Library (http://fragglet.github.io/c-algorithms/) offers a Trie implementation in C. It's open-source with a BSD-style license.

A suffix tree implementation in C can be found here: https://github.com/0xtonyxia/suffix-tree

I hope that helps.

Solution 2

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

typedef struct trie trie;
struct trie
{
       char key;
       trie *next,*children;
};

trie *newnode(char s)
{
     trie *t=(trie *)malloc(sizeof(trie));
     t->key=s;
     t->next=t->children=NULL;
}

void insert(trie **t,char *s,int start)
{if(s[start]=='\0')
                   {
                          *t=newnode('#');
                          return;
                   } 
                   if(*t==NULL)
                   {
                               *t=newnode(s[start]);
                               insert(&(*t)->children,s,start+1);
                   }       
                   if((*t)->key==s[start])
                   insert(&(*t)->children,s,start+1);
                   else
                   insert(&(*t)->next,s,start);
}


bool search(trie *t ,char *s,int start)
{


     if(t==NULL)
     return false;

     if(t->key=='#' && s[start]=='\0')
     return true;

     if(t->key!='#' && s[start]=='\0' || t->key=='#' && s[start]!='\0')
     return false;

     if(t->key==s[start])
     return search(t->children,s,start+1);

     else
     return search(t->next,s,start);

     return false;
}

/*void push(trie **t ,char *str)
{                        int i=0;
                         for(i=0;i<strlen(str);i++)
                         insert(t,str[i]);
}*/

main()
{     int i=0;

      trie *t=NULL;
      char ch='y';
      while(ch=='y')
      {             
                    {char str[20];
                    fflush(stdin);
                    printf("Enter the word ");
                    gets(str);


                    insert(&t,str,0);
                    }
                   // push(&t,str);
                    fflush(stdin);
                    printf("more y/n ::");
                    ch=getchar();
      }

      ch='y';
      while(ch=='y')
      {char str[20];
      fflush(stdin);
      printf("Enter the string you want to search::");
      gets(str);

      fflush(stdin);
      if(search(t,str,0))
      printf("Found");
      else
      printf("Not Found");

      printf("\n more y/n ::");
      scanf("%c",&ch);

      }

    getch();  

}

Solution 3

Here are the links that I have found to be very helpful.

6 hour lecture on suffix trees (Lecture 3 to Lecture 5) Google SCICOMP Lecture 5 (Longest common substring problem: O(n) suffix tree, sorting suffixes)

Generalized Suffix Tree Implementation http://www.geeksforgeeks.org/generalized-suffix-tree-1/

Fast String searching with suffix tree http://marknelson.us/1996/08/01/suffix-trees/

Look up Ukkonen algorithm on wikipedia. Note: Can't post more than 2 links cause not enough reputation.

Comments

[Shaggy Frog]

possible duplicate of tries data structure implementation......... Application - Dictionary............

[AnyOneElse]

How about closing this question by chosing an answer? Since you asked the same question right away this one is definitely redundant.

[stan0]

The wikipedia articles on Trie and Suffix tree provide good explanations and pseudocode for Trie

[Robert]

Could you provide some context?

[Greg S]

@Rasmi Ranjan Nayak: links are now fixed