问题标签 [suffix-tree]

这是一个简单的问题，我正在实现后缀数组，但我被困在这里：

这段代码无法编译，第三行有错误，谁能帮帮我？感谢：D

更新：我的错，我忘了包括第一行，对不起，这是我的第一个问题：P

我已经基于此处的站点http://marknelson.us/1996/08/01/suffix-trees/在 Java 中构建了一个后缀树，但我遇到了一个问题。我可以很好地构建后缀树，但我可以尝试从树中构建一组所有后缀。我基本上找到了所有的“结束节点”并返回由那个“结束节点”表示的字符串

该算法适用于“簿记员”之类的词

后缀：

但是当我使用“ATATATATATA”之类的东西时它会失败

后缀：

但正确的后缀应该是：

我可以通过查找每个“结束节点”字符串的所有后缀来找到答案，但这似乎不是正确的方法。还有其他建议吗？

编辑：谢谢izomorphius！在原始字符串中添加 END_CHAR 帮助了很多。

后缀：

我对 python 比较陌生，并且开始使用后缀树。我可以构建它们，但是当字符串变大时我遇到了内存问题。我知道它们可用于处理大小为 4^10 或 4^12 的 DNA 字符串，但每当我尝试实现一种方法时，都会遇到内存问题。

这是我生成字符串和后缀树的代码。

当我达到 4**8 左右时，我遇到了严重的内存问题。我对此很陌生，所以我确定我在存储这些东西时遗漏了一些东西。任何建议将不胜感激。

注意：我想做字符串搜索以在一个非常大的字符串中查找匹配的字符串。搜索字符串匹配大小为 16。因此，这将在一个大字符串中查找大小为 16 的字符串，然后移动到下一个字符串并执行另一次搜索。由于我将进行大量搜索，因此建议使用后缀树。

非常感谢

'canonize' 函数（下面给出，来自 Ukkonen 的论文）是如何工作的，特别是 while 循环何时完成？我认为 p' - k' 的值将始终小于 p - k 的值。我是对还是错？

目前我正在使用两个嵌套for循环来生成字符串的所有子字符串。我听说过，Suffix Tree但 AFAIKSuffix Tree生成后缀而不是子字符串。以下是我目前正在使用的代码 -

我想要一种可以生成小于的所有子字符串的方法O(n^2)。尽管通过查看我的代码，任何人都可以建议我这是不可能的，因为我正在将每个子字符串添加到列表中。但我的目标不是存储所有子字符串，我的目标是找到一个在字典上是最小字符串的字符串。

谁能给我一个关于如何以及何时在后缀树中创建后缀链接的示例？

如果我的字符串是ABABABC，但如果这样更好，请使用不同的示例。

希望给一些图片来说明每一步。

非常感谢。

解决这个问题的最佳方法（性能方面）是什么？我被推荐使用后缀树。这是最好的方法吗？

创建字符串“ABAB”的后缀树时，我只得到 2 个节点：

ABAB 和 BAB

最长的重复子字符串（“AB”）应该位于“具有至少 k 个后代的最深节点”，但我的字符串不是这种情况，这里有什么问题？

谢谢

当在字符串 ' AEKEAAEKEAAEKEA$' 上运行算法以寻找至少出现 3 次的最长子字符串时，后缀树中的所有节点最多有 2 个分支，这怎么可能？

正确的结果应该是子字符串 ' AEKEA'。

您可以在 在线后缀树生成器中轻松查看树

我只是按照维基百科的描述：

“找到至少出现k次的最长子串的问题，可以通过首先对树进行预处理来计算每个内部节点的叶子后代的数量，然后找到至少有k个后代的最深节点”

我在这里想念什么？

谢谢你。