c++ - 后缀树构造

Question

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

struct suffix
{

char  letter;
suffix * left,*right; 

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

}

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

Answer 1

看看维基百科的描述：

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

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

最后，不要在这里使用指针。他们什么也没给你买，只会给你带来麻烦。改用 a 之类的东西boost::container::vector<suffix>（我建议 a std::vector<suffix>，但不幸的是标准库容器不能处理不完整的类型）。

Answer 2

维基百科是一个开始。

然而实际做的却是了解后缀树构造算法，Weiner 或 Ukkonen 算法。

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

这个链接也不太学术，更实用： http ://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm

尝试开始理解算法。

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

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