suffix-tree

3热度

2回答

概念上简单的线性时间后缀树构造

1973年，韦纳给出了第一个后缀树的线性时间构造。该算法在1976年由McCreight简化，在1995年由Ukkonen简化。尽管如此，我从概念上找到了Ukkonen的算法。自1995年以来是否对Ukkonen的算法进行了简化？

16热度

1回答

python：用于广义后缀树的库

我需要可以构建后缀树和特别是通用后缀树的python库。你能建议我一些图书馆吗？谢谢。

1热度

1回答

从后缀树生成后缀

我已经基于此处的网站构建了一个基于Java的后缀树http://marknelson.us/1996/08/01/suffix-trees/但我遇到了问题。我可以建立一个后缀树，但我可以尝试从树中构建一组所有后缀。我基本上找到所有的“端节点”和由“末端节点”返回的表示字符串该算法适用于一个字，如“会计” ├── (1) bookkeeper ├── (9) e │ ├── (8) eper

4热度

1回答

我可以生成复杂度为<O（n^2）的所有子字符串

目前我使用两个嵌套for循环来生成字符串的所有子字符串。我听说Suffix Tree，但AFAIK Suffix Tree生成后缀不是子字符串。以下是目前我正在using- String s = "abacbccca"; int l = s.length(); for (short c = 0; c < l; c++) { for (short r = 0;

2热度

3回答

完整的后缀数组

后缀数组将索引给定字符串列表的所有后缀，但是如果您要索引所有可能的唯一子字符串，该怎么办？我在这个有点新的，所以这里是我的意思的例子：鉴于串 abcd 后缀数组索引（至少我的理解） (abcd,bcd,cd,d) 我想索引（所有的子串） (abcd,bcd,cd,d,abc,bc,c,ab,b,a) 是我想找的后缀数组吗？如果是这样，我该如何获取所有的子字符串索引？如果不是，我应该在

9热度

6回答

找到最长的重复子串

解决这个问题时最好的方法是什么？我被推荐使用后缀树，这是最好的方法吗？

3热度

2回答

后缀树库C++与简单的例子如何使用它

我正在寻找后缀树库（线性时间构造），我发现所有是PATL，但PATL没有文档，我无法弄清楚任何一个例子。那么有没有一个后缀树库的c + +有一个体面的文档？ PATL家： http://code.google.com/p/patl/ 编辑：动机：我需要处理大量的字符串，找到经常共同子串，并报告如有子的n多出现t秒内发生。我实现了一个树（在节点中有计数器，实际上它不是一个计数器，而是一个std

2热度

2回答

后缀树构造

我要去实现后缀树给定的字符串，我想应该delcared这样 struct suffix { char letter; suffix * left,*right; }; suffix *insert(suffix *node,char *s){ } //我在这里要构建树子的所有出现和人物但不知道如何使用左边和右边的部分，这棵树是按照二进制搜索树的字符严格排序排列和排列的吗？或

-2热度

1回答

这行代码在这段代码中做了什么？

我发现下面的代码在网上为后缀树 #include <stdio.h> #define E 0 struct suffix_tree_node; struct suffix_tree_link { // 0 is e - global index of during string's end unsigned long start; unsigned lon

3热度

1回答

搜索树/ trie时返回多个节点？

我构建了一个后缀trie，一个包含所有字符串后缀的树，其中每个节点只包含一个字符，每个路径末尾都有一个SuffixNode，后缀包含字符串中后缀的位置。假设我的trie包含单词“Cat”，“Car”和“Can”，并且我想搜索“Ca”，结果应该返回3个后缀节点，因为搜索字符串位于3个不同的地方。我设法搜索树“Ca”，但是一旦我达到那个点，我不知道如何继续遍历'a'节点的子节点来查找所有后缀节点。