尝试和后缀树实现
我学习了Tries和Suffix Trees，并想实现它。 请分享一些链接，我可以从中了解实施的结构和基本思路。
任何好的例子，如果包括，将是一个加号。
在C中实现
C算法库（http://fragglet.github.io/c-algorithms/）提供了C语言的Trie实现。它是开源的，带有BSD风格的许可证。
C中的后缀树实现可以在这里找到：https：//github.com/0xtonyxia/suffix-tree
我希望有所帮助。
#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();
}
以下是我发现的非常有用的链接。
6个小时的后缀树讲座（第3讲到第5讲）Google SCICOMP第5讲（最长公共子串问题：O（n）后缀树，排序后缀）
通用后缀树实现http://www.geeksforgeeks.org/generalized-suffix-tree-1/
用后缀树快速搜索字符串http://marknelson.us/1996/08/01/suffix-trees/
在wikipedia上查找Ukkonen算法。 注意：不能发布超过2个链接会导致声誉不够。
链接地址: http://www.djcxy.com/p/40093.html