问题标签 [suffix-tree]

我已经实现了一个未压缩的后缀树。我想知道如何解决在字符串中查找最长重复子字符串的问题。我知道我们必须找到有两个孩子的最深的内部节点，但是如何编码。另外，我们如何知道最长的重复子串是什么。我对 JAVA 中的代码很感兴趣。请给出java实现。作为参考，我的 TrieNode 看起来像

我正在研究一个必须找到最长重复子字符串的 php 脚本。我发现了这个后缀树的东西。我正在尝试实现 Ukkonnen 的算法，但我不知道何时以及如何扩展树。

如果我有不在树中的新字符也没关系，但我必须从根创建一个新节点和 egde。但是我怎么知道我是否必须分裂一个边缘？

我找到了它的 C++ 实现（链接），我试图将它翻译成 php，但我想我有一个 typeo，因为它给出了一个几乎很好的结果，问题是我无法修复它，直到我没有完全理解它...

我阅读了十几个关于 Suffix-Trees 的描述，但其中一些并没有深入到其中，另一些则在第二句之后让我头疼。

这是我现在拥有的代码：Suffix-tree.php（对不起，这个编辑器不能接受它）我用这个网站来检查结果。

所以任何建议将不胜感激......

编辑：我从提到的网站上找到的 JavaScript 内容重写了它。这是源代码的链接：Suffix-Tree v0.1

JavaScript 中是否有一个很好的后缀树实现？需要一个字符串（和一个分隔符）并制作适当的后缀树的东西？

有人知道下面声明的原因吗？或者有没有更好的网站来问这类问题？任何指针将不胜感激。

如果一个模式在文本（长度为 n）中出现 k 次，则在该文本的后缀树中搜索所有这些 k 次模式的成本为 O(n+k)。

给定一系列操作：

a*b*a*b*a*a*b*a*b

有没有办法获得最佳细分以启用子字符串的重用。

制造

a*b*a*b*a*a*b*a*b => c*a*c，其中 c = a*b*a*b

然后看到

a*b*a*b => d*d，其中 d = a*b

总而言之，将 8 个初始操作减少到此处描述的 4 个？

(c = (d = a*b)*d)*a*c

目标当然是最小化操作次数

我正在考虑一种后缀树。

我对线性时间启发式或解决方案特别感兴趣。'*' 操作实际上是矩阵乘法。

我读过：

在 txt[1..n] 中搜索子字符串 pat[1..m] 可以在 O(m) 时间内解决（在 O(n) 时间内构建 txt 的后缀树之后）。

但是在每一点，我们都必须选择要采用哪个分支，所以就像在 n 叉树中一样，在每个节点上，我们必须与该节点中的所有最大 n 个指针进行比较，以决定采用哪个分支。这会不会在这个算法的复杂性中带来 n 个因素，不知何故在图片中

那么上面如何说可以在 O(m) 中找到子字符串？

我在这里想念什么？

我试图在一个字符串中找到最长的回文。蛮力解决方案需要 O(n^3) 时间。我读到有一个使用后缀树的线性时间算法。我熟悉后缀树并且很乐意构建它们。你如何使用构建的后缀树来找到最长的回文。

两个密切相关的数据结构是后缀树和后缀数组。根据我的阅读，后缀树比后缀数组更快、更强大、更灵活、内存效率更高。但是，在这个较早的问题中，最重要的答案之一提到后缀数组在实践中得到了更广泛的使用。我没有任何使用这些结构的经验，但现在对于需要它们提供的功能的问题（例如快速子字符串检查），我似乎总是更喜欢后缀树而不是后缀数组。

在什么情况下后缀数组比后缀树更可取？

（顺便说一下，虽然这个问题与我所链接的问题有关，但我认为这不是一个完全重复的问题，因为我只对后缀数组和后缀树的比较感兴趣，完全不考虑尝试. 但是，如果您不同意，我会理解这个问题是否要关闭。）

我正在实现一个后缀树（这与后缀树不同），它将字符串的字符后缀存储为树结构中的节点，其中通过遍历树直到你点击'$'或者你点击您的搜索结束。

问题在于，在使用大型文本文件时，构造这个 trie 会比 Java 消耗更多的内存。有没有什么地方可以减少数据结构方面的内存使用？这是家庭作业，不需要将其制成压缩后缀树（基本上是后缀树）。

这是我目前拥有的基本结构（如果你真的想要，我可以提供实现细节）：

// SuffixTrie.java

每个节点是：

每个节点中保存的数据是：

我得到的错误是：

虽然它适用于较小的文本文件，但这是他们第一次给学生这个作业，所以教师不知道这是否可以使用后缀 trie..

要构建后缀树，在最坏的情况下，如果字符串的所有字母都不同，那么复杂度将类似于

这是O（n ^ 2）。

然而，根据http://en.wikipedia.org/wiki/Suffix_tree构建后缀树需要 O(n) 时间。我在这里想念什么？