问题标签 [suffix-tree]

我一直在尝试确定后缀树或后缀数组（包括它们的变体）是否更节省空间（在下面给出的其他属性中），但我似乎根据我的看法提出了不同的观点。例如，这篇wikipedia article建议后缀数组更节省空间。在本书中，在第 1.6 节中，基于 Kunihiko Sadakane 的论文“具有完整功能的压缩后缀树”，建议（压缩）后缀树对空间非常有效。那么关于后缀树和后缀数组（包括它们的变体）之间比较的最新研究是什么？更具体地说，我有兴趣知道在 i) 构造、ii) 空间（理论和实践）、iii) 查询性能方面哪个更好。

我知道这个问题的一部分之前可能已经被问过，但这些问题至少有一年的历史了，我对最新的研究很感兴趣。

我看到了维基百科页面，但仍然不清楚这个想法。

为了找到 2 个字符串 (T和S) 的最长公共子字符串，我读到我们必须为字符串 构建一个后缀树T($1)S($2)，其中`($1) 和 ($2) 是不属于字符串的特殊字符。

但是字符串的维基百科图像ABAB看起来BABA像这样：

为什么它不包含整个字符串ABAB($1)BABA($2)？不是拼接字符串的后缀吗？

叶子上的数字是什么？

处理一个给定 SuffixTree 作为输入的函数，输出该后缀树中的整数列表。例如。getIndices tree1 = [2,4,1,3,5,0] 。整数列表的顺序无关紧要。我在函数的倒数第二行收到错误：“ Couldn't match expected type 'SuffixTree' with actual type '[SuffixTree]'”。我已经考虑了很长时间，但没有运气。任何帮助将不胜感激。

我正在开发一个程序来查找多个字符串之间最长的公共子字符串。我已经降低了使用后缀数组或后缀树的方法。我想看看哪种方法更好（如果有的话）以及为什么。同样对于后缀数组，我已经看到了一些针对两个字符串的算法，但对于两个以上的字符串却没有。任何可靠的例子将不胜感激，再次感谢您的建议！

注意：我没有看到任何其他专门解决此问题的问题，但如果存在，请指出我的方向！

我正在尝试使用 ukkonen 的后缀树来比较文档。

在这一点上，我关心两件事：

1. 首先，我尝试为一个文档生成后缀树，然后使用该后缀树来查找该文档中的所有常见子字符串。

2. 接下来是识别两个文档之间的所有公共子字符串。

我能够为基于http://marknelson.us/1996/08/01/suffix-trees/的文档生成 ukkonen 后缀树。并搜索给定的子字符串。但是我仍然找不到一种方法来识别给定文档中的所有公共子字符串。你能告诉我一种方法吗？我正在使用Visual C++。

我们可以使用 ukkonen 的算法来比较两个文档并识别它们之间的所有公共子字符串吗？如果是这样，请逐步解释。

Ukkonen's suffix tree algorithm in plain English对Ukkonen's suffix tree有很好的解释吗？

我需要为最长的两个模式前缀/后缀匹配编写算法，其时间复杂度为 O(n+m1+m2)，其中 n 是字符串的长度，m1，m2 分别是模式 1 和模式 2 的长度。

示例：如果 String 是“OBANTAO”，Pattern1 是“BANANA”，Patten2 是“SIESTA”，那么答案是 String 的子字符串“BANTA”，由 BANANA 的前缀 BAN 和 SIESTA 的后缀 TA 组成。

来自 Google 的结果是：“Rabin-karp 字符串搜索算法”、“Knuth-morris-pratt 算法”和“Boyer-moore 字符串搜索算法”。

我能够理解上述所有 3 种算法，但问题是，它们都是基于“单一模式前缀/后缀匹配”的。我无法将它们扩展为两个模式前缀/后缀匹配。

一个示例算法或搜索它的链接将对我开发程序有很大帮助。

我在打印后缀树中最长的公共子串时遇到困难。我可以轻松计算最长公共子串的长度，但在实际找到子串时遇到问题。下面是 C++ 中最长公共子串的代码。谁能帮忙我出去？

我已经用简单的英语阅读了 Ukkonen 的后缀树算法的帖子？. 但目前尚不清楚如何使用该算法获得叶子标签。

在后缀树中，叶子标签是数字 i，使得 S[i..n] 是叶子表示的后缀。如果我想要这样的标签，总复杂度仍然是 O(n) 吗？

怎么做？

如果有人详细解释原因以及在哪种情况下一种比另一种更有利，那将有很大帮助。提前致谢 ！！

我用java语言创建了一个后缀树。我们知道后缀树的应用之一是从树中搜索字符串。所以我的问题是，如何遍历后缀树的每个节点以查找后缀树中是否存在搜索字符串。

先感谢您。