首页 文章

后缀树构造

提问于
浏览 次
2

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

struct suffix
{

char  letter;
suffix * left,*right; 

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

}

//这里我将构建一个包含所有子串和字符的树，但不知道如何使用左右部分，这个树是通过二进制搜索树等字符的严格排序来排序和排列的？或者？请帮助我，我不要想在网上使用一些代码，我需要实现它的myselft，所以请给我一些提示，一些小代码

c++ suffix-tree

2 回答

  • 4

    维基百科是一个开始 .

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

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

    此链接的学术性和实用性也较低：http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm

    尝试开始理解算法 .

    好运之后，这是最棘手的数据结构之一 . 唯一最糟糕的是后缀树的压缩和优化版本 .

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

    回复于
  • 4

    看看Wikipedia description：

    Suffix tree

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

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

    最后，don’t use pointers在这里 . 他们什么也买不到，只会造成麻烦 . 使用像 boost::container::vector<suffix> 之类的东西（我建议 std::vector<suffix> ，但不幸的是standard library containers cannot deal with incomplete types） .

    回复于

相关问题