后缀树的建设

2018-06-14 02:03:35

我将为给定的字符串实现后缀树，我认为它应该像这样去除

struct suffix
{

char  letter;
suffix * left,*right; 

};
suffix *insert(suffix *node,char *s){

}

//这里我要构造出所有子字符串和字符的树，但不知道如何使用左右部分，这棵树是按照二叉搜索树的字符严格排序排序和排列的吗？或者？请帮助我，我不会想要在网上使用一些代码，我需要自己实现它，所以请给我一些提示，一些小代码

维基百科是一个开始。

然而实际上这样做是为了理解后缀树构造算法，Weiner或Ukkonen算法。

Ukkonen算法更简单：http://europa.zbh.uni-hamburg.de/pubs/pdf/GieKur1997.pdf

此外，这个链接学术性较差，更实用：http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm

尝试开始理解该算法。

幸运之后，这是最难的数据结构之一。唯一最糟糕的是后缀树的压缩和优化版本。

但所有优秀的程序员都喜欢大挑战。

看看维基百科的描述：

后缀树

请注意，首先，后缀树不是二叉树，因此您的实现大纲根本上是有缺陷的。

接下来，仅为每个节点/分支存储单个字符是不够的; 后缀树分支表示可以比单个字符更长的子字符串。通常在字符串中存储子字符串的开始和结束索引，而不是字符串本身; 否则后缀树会消耗大量不必要的内存。

最后，不要在这里使用指针。他们什么都不买，只会造成麻烦。使用类似boost::container::vector<suffix> （我建议使用std::vector<suffix> ，但不幸的是标准库容器不能处理不完整的类型）。

链接地址: http://www.djcxy.com/p/40107.html