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.

Answer 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.

Answer 2

#include <iostream>
#include <string.h>
using namespace std;
int high;
struct stnode
{
    stnode* ptr[27];
    int start;
    int end;
    stnode(int s,int e)
    {
        for (int i = 0; i < 27; ++i)
        {
            ptr[i]=NULL;
        }
        start=s;
        end=e;
    }
}*root=NULL;


stnode* fun(stnode* child,string str,int ind)
{
    int s=child->start;
    while(s<=child->end&&str.at(s)==str.at(ind))
        {
            s++;
            ind++;
        }
    if(s<=child->end)
    {
        child->ptr[str.at(ind)-'a']=new stnode(ind,high);
        if(str.at(s)=='$')
            child->ptr[26]=new stnode(s,child->end);
        else
            child->ptr[str.at(s)-'a']=new stnode(s,child->end);
        child->end=s-1;
        return child;
    }
    else
    {
        if(child->ptr[str.at(ind)-'a'])
        {
            child->ptr[str.at(ind)-'a']=fun(child->ptr[str.at(ind)-'a'],str,ind);
            return child;
        }
        else
        {
            child->ptr[str.at(ind)-'a']=new stnode(ind,high);
            return child;
        }
    }

}



stnode* create(stnode* root,string str,int ind)
{
    if(!root)
    {
        root=new stnode(ind,high);
        return root;
    }
    if(str.at(ind)=='$')
    {
        root->ptr[26]=new stnode(ind,high);
        return root;
    }
    if(!root->ptr[str.at(ind)-'a'])
    {
        root->ptr[str.at(ind)-'a']=new stnode(ind,high);
        return root;
    }
    root->ptr[str.at(ind)-'a']=fun(root->ptr[str.at(ind)-'a'],str,ind);
    return root;
}



void display(stnode* root,string str)
{
    if(!root)
        return;
    if(root->start!=-1)
    {
        for(int i=root->start;i<=root->end;i++)
        {
            cout<<str.at(i);
        }
        cout<<"\n";
    }
    for(int i=0;i<27;i++)
    {
        display(root->ptr[i],str);
    }
}


int main(int argc, char const *argv[])
{
    string str;
    cout<<"enter the string.\n";
    cin>>str;
    str=str+"$";
    high=str.length()-1;

    root=new stnode(-1,-1);

    for(int i=str.length()-1;i>=0;i--)
    {
        root=create(root,str,i);
        display(root,str);
        cout<<"\n\n\n";
    }

    return 0;
}

Answer 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.

Answer 4

#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();  

}