问题标签 [suffix-tree]

这是输入文本“mississippi”的后缀树的可视化图表。在此示例中，我要搜索的关键字是“si”。我想我明白如何获得“si”的第一个索引

• 从根节点 #1 开始
• 第一条边是“s”，所以我们向下移动到节点#2
• 节点#2 的第二条边是“i”，因此我们检索节点#7，并且该节点将索引存储到文本中。

但是现在对于“si”的第二次出现......我是否继续沿着子树 #7 搜索下一次出现？对我来说真的没有意义。

或者，是否必须以不同的方式组装树才能支持多个索引？

输入：字符串 S = AAGATATGATAGGAT。

输出：最大重复，例如 GATA（如位置 3 和 8）、GAT（如位置 3、8 和 13）等等......

• 最大重复是子串 t 在 S 中出现 k>1 次，如果 t 向左或向右扩展，它将出现少于 k 次。

• 内部节点的叶子后代是后缀，每个后缀都有一个左字符。

• 如果所有叶子后代的左字符不完全相同，则称为“左多样化”节点。

• 最大重复是左多样化的内部节点。

总体思路：

• 构建后缀树，然后在树上进行 DFS（深度优先搜索）

• 对于每片叶子，用它的左边字符标记它

• 对于每个内部节点：

• 如果至少有一个孩子标有 *，则标有 *

• 否则，如果其子标签多种多样，则使用 * 进行标签。

• 否则所有孩子都有相同的标签，将其复制到当前节点

上述想法是否正确？伪代码如何？然后我可以尝试自己编写程序。

我已经了解到，后缀树对于许多与字符串相关的任务来说是极好的和有用的结构，我想了解更多关于它们的信息。任何人都可以建议一个很好的起点来理解这些事情吗？也就是说，我不需要一些现成的代码或实现它的库，但可能需要一些教程来展示它们是如何构建的，以及你可以用它们做什么。我喜欢“娱乐性编程”，后缀树在我要学习的东西清单上很重要 :)

PS：我更喜欢 Delphi/pascal，但欢迎任何语言的教程。

是否有用于在 C++ 中构建后缀树的 Ukkonen 算法的实现？任何高级语言的实现也很好。

这是一道面试题：

给定一个字符串，找出它的所有排列是字典中的一个单词。

我的解决方案：

将字典中的所有单词放入后缀树中，然后在树中搜索字符串的每个排列。

搜索时间是O(n)，其中n是字符串的大小。但是字符串可能有n!排列。

如何提高效率？

前段时间我发布了一个关于从磁盘保存/检索后缀树的问题。终于可以正常工作了，但是现在构造非常缓慢，我现在不想弄乱 Ukkonen 算法（线性构造）。

因此，我想进行并发插入以加速该过程，而不必使树线程安全。

后缀树按其初始字符存储单词（看我上一个问题上发布的图像），因此，单词 Banana 位于根节点的“B”子节点中，Apple 将位于“A”子节点中，依此类推. 因此，插入以“B”开头的单词永远不会干扰以“A”开头的插入。我的想法是为要插入的单词集的每个初始字符都有一个线程：一个线程插入'A'，另一个线程插入'B'，等等。

所以我在考虑一个Executer类，它只是将单词添加到每个单词的队列中 Process（如果它不存在，首先创建它）。

类Process是进行插入的类。每个Process实例都是一个独立的线程，其中Queue包含仍然需要插入的单词。

在这个Process类中我遇到了麻烦，我猜它应该继承自threading.Thread，因为每个实例都应该是一个线程，但是在所有文本处理完成之前我如何让它保持活力呢？我的意思是，它应该从它Queue的单词中插入单词，但是当Queue为空时，线程不应该死，只是继续等待，直到更多的单词填充Queue，“唤醒”并继续插入。

假设我有一个字符流作为我的输入。

在添加每个新字符而不重新处理
整个字符串 之后，找到最长回文子串的最佳方法是什么？

在每个新字符出现后，我想避免重复
以前处理过的字符串。

有没有我可以使用的树数据结构：
1. 我不会从每个新角色开始重建。
2. 随着字符串越来越长，我可以在哪里移动节点和离开。

构建两棵树怎么样，一棵用于字符串（前缀树），
另一棵用于字符串的逆（后缀树）？

只是想知道您是否知道 python 中任何基于 C 的扩展可以帮助我在线性时间内构建后缀树/数组？

维基百科定义了很多人们可以使用的表情符号。我想将此列表与字符串中的单词匹配。我现在有这个：

输出：

所以原则上这是可行的。但是，我有两个问题：

1. 如您所见，我在数组中的每个表情符号周围都放置了空格，例如 ':-)' 而不是 ':-)' 在我看来，这会降低数组的可读性。有没有办法在没有空格的情况下存储表情符号，但仍然与周围有空格的 $string 匹配？（和现在的代码一样高效吗？）

2. 或者有没有办法将表情符号放在一个变量中，并在空间上爆炸以检查 $string？就像是

   $emoticons = array( '[HAPPY]' => ">:] :-) :) :o) :] :3 :c) :> =] 8) =) :} :^)", '[悲伤] ' => ":'-( :'( :'-) :')" //等等...

3. str_replace 是最有效的方法吗？

我问是因为我需要检查数百万个字符串，所以我正在寻找最有效的方法来节省处理时间:)

我一直在为我的工作阅读 Ukkonen 的后缀树，并想确认以下内容是否属实。

在 Ukkonen 后缀树中这样说是否正确：

只有通向叶节点的边才能将多个连续字符压缩为其中的一部分。并且内部节点之间的边（例如，从根到内部节点）只能代表一个字符。