问题标签 [suffix-tree]

我正在阅读Tries通常称为前缀树和Suffix Trees.
虽然我找到了 a 的代码，但Trie我找不到 a 的示例Suffix Tree。我也觉得构建 a 的代码与 a 的代码Trie相同，Suffix Tree唯一的区别是在前一种情况下我们存储前缀但在后缀中。
这是真的？任何人都可以帮我清除这个问题吗？一个示例代码会很有帮助！

只是一个简单的问题：

请问后缀树（存储单词后缀的树）是一种b-tree吗？

我正在尝试解决 2 个字符串之间的最大公共子字符串的问题。我将把我的问题简化为以下内容：我创建了一个通用后缀树，根据我的理解，最大的公共子字符串是由属于两个字符串的节点组成的最深路径。

我的测试输入是：

看来我构建的树是正确的，但我的问题是以下方法（我最初通过树的根）：

我的目标是，为了找到属于两个字符串的节点的最深路径，我将遍历树（预排序）并在列表（current）中添加属于两个字符串的节点。一旦我在一个不属于两者的节点中，我会更新max列表（如果current更大）。

但是代码是错误的。而且我对如何实现这一点感到困惑，因为我已经很久没有为一般（非二元）树编写代码了。

你能帮我解决这个问题吗？

更新：
根据@templatetypedef 修改。也无法完成这项工作。

我遇到了一个问题，它需要一个数据结构来保存字符串 S 并允许我：

1. 在 O(|W|) 时间内检查单词 W 是否是 S 的子词
2. 在 O(|U|) 时间内找到 S 的最长后缀，它也是给定单词 U 的前缀
3. 在 O(|K|) 时间内在 S 的末尾追加字符串 K

我发现由 Ukkonen 算法构建的后缀树是我正在寻找的。算法被描述为“后缀树的在线构建”，我对“在线”部分有一个问题：插入每个字符后，算法构造一个隐式后缀树，可以在最后一步转换为显式。但是如果我想在这一步之前使用隐式树进行搜索呢？“在线”表明在插入分析字符串的任何前缀之后是可能的，但我找不到任何在隐式树上运行的最简单算法的示例。

我的问题是：如何在隐式后缀树中搜索字符串？

编辑：我接受了一个很好的答案来解决我的问题，但同时我设法找到了一个更简单的解决方案 2：在长度为 S 的后缀中搜索 U 就足够了 |U| 使用KMP算法，最后匹配的字符数将是字符串重叠。

输入：两个字符串 A 和 B。

输出：一组重复的、不重叠的子串

我必须找到所有重复的字符串，每个字符串都必须在两个（！）字符串中至少出现一次。例如，让

A = "xyabcxeeeyabczeee" 和 B = "yxabcxabee"。

那么一个有效的输出将是 {"abcx","ab","ee"} 但不是 "eee"，因为它只出现在字符串 A 中。

我认为这个问题与“超最大重复”问题非常相关。这是一个定义：

最大重复对：S 中的一对相同的子串 alpha 和 beta，这样在任一方向上扩展 alpha 和 beta 都会破坏两个字符串的相等性它表示为三元组（位置 1，位置 2，长度）

最大重复：“出现在 S 中的最大对中的 S 的子串”。示例：S 中的 abc = xabcyiiizabcqabcyrxar。注意：可以有许多最大重复对，但只能有有限数量的最大重复。

超最大重复“永远不会作为任何其他最大重复的子串出现的最大重复”示例：S 中的 abcy = xabcyiiizabcqabcyrxar。

查找所有超最大重复的算法在“字符串、树和序列的算法”中进行了描述，但仅适用于后缀树。

它的工作原理是：1.) 使用 DFS 查找所有左分集节点

对于 S 中的每个位置 i，S(i-1) 称为左字符 i。T(S)中叶子的左字符是该叶子表示的后缀位置的左字符。如果在 v 的子树中至少有两个叶子具有不同的左字符，则 T(S) 中的内部节点 v 称为左分集。

2.) 在这些节点上应用定理 7.12.4：

当且仅当 v 的所有子节点都是叶子并且每个子节点都具有不同的左字符时，左多样化内部节点 v 表示超最大重复 a

字符串 A 和 B 可能都必须连接起来，当我们在第二步中检查 v 的叶子时，我们还必须施加一个额外的约束，即字符串 A 和 B 中必须至少有一个不同的左字符。这可以通过将它们的位置与 A 的长度进行比较。如果位置（左字符）> 长度（A），则左字符在 A 中，否则在 B 中。

你能帮我用后缀 + lcp 数组解决这个问题吗？

我在文本 T 中找到最长的子字符串，因此它是字符串 S 的前缀。我使用后缀树制作了算法，它提供了不太复杂的解决方案，但由于 Matlab 不使用指针或任何其他引用，我被困在执行。

有人可以建议一些解决方案或一些替代方法来解决这个问题，可能在 Matlab 中。

是否有从字符串 S[1..m] 的后缀树生成字符串 S[2..m] 的后缀树的快速（O(1) 时间复杂度）方法？

我熟悉 Ukkonen，所以我知道如何从字符串 S[1..m] 的后缀树制作字符串 S[1..m+1] 的快速后缀树，但我无法将算法应用于相反的情况.

我需要一个后缀树 Java 实现。经过一番谷歌搜索后，我得出结论，libdivsufsort C 实现是最好的。是否有相同（或几乎一样好）质量的 Java 实现，并且最好是开源的。实现应该是生产代码，而不是概念验证代码。

我查阅了很多文献，但我没有找到任何关于将子字符串删除或插入到后缀树中的信息。只有 Ukkonen 或 McCreight 的算法用于构建树。
最糟糕的方法是在删除或插入子字符串后重建树。但我认为这是一种最好的方法。
例如（位置从 0 开始计算）：
我有带有“abcdef”的后缀树，我需要删除从 1 到 3 的符号。然后我将拥有带有“aef”的后缀树。然后我需要从位置 1 添加字符串“as”。在此之后，我将拥有带有“aasef”的后缀树。你能帮助我吗？

我了解ukkonen 的算法。我只是好奇如何将其扩展为包含多个字符串（以特殊字符“$”结尾）。

我在某处读到给定字符串 s1（比如“abcddefx$”）和 s2（比如“abddefgh$”），我应该通过 ukkonen 的算法正常插入 s1。然后用 s2 遍历树。那就是我应该在树中搜索 s2 。一旦我到达搜索结束的节点（“ab”，在“b”之后），我应该从那里恢复 ukkonen 算法。

我理解这背后的基本逻辑。但我很好奇的是，旧的后缀链接会发生什么。他们还有效吗？？？我也对我的三元组（active_node，active_length，remainder）感到困惑（节点代表“ab”，0,0），因为我开始新的通道？？？