Tries and Suffix Trees implementation
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.
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.
#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]==' ')
{
*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]==' ')
return true;
if(t->key!='#' && s[start]==' ' || t->key=='#' && s[start]!=' ')
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();
}
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.
链接地址: http://www.djcxy.com/p/40094.html上一篇: 使用后缀树进行近似子串匹配
下一篇: 尝试和后缀树实现