找到一个关键字的所有指标的后缀树

Question

这是一个后缀树为输入文本“密西西比”的视觉图。在这个例子中，我正在搜索的关键字是“si”。我想我明白如何得到的“SI”

• 在根节点＃开始的第一指标1
• 第一边缘为“S”，所以我们旅行下来到节点＃2
• 的第二边缘节点＃2是“我”，因此我们检索节点＃7，并且该节点将索引存储到文本中。

但是现在对于“si”的第二次出现......我是否继续向下搜索子树＃7以查找下一个出现？对我来说真的没有意义。

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

Answer 1

问题是您在树中没有足够的信息。

其导致标记6该节点的路径表示既（通常，所有）在原来的字出现。你想要做的是当你按照算法描述的处理前缀时，你想要在节点中存储索引。一般来说，算法不会存储这些信息，但很容易对其进行修改。

每次访问节点时，都要将原始字符串中的位置追加到匹配位置列表中。

1. （空树）
2. （路径 “SI”，节点 “6”（在附加 “6” 节点信息：4-5），树的其余部分）
3. 等
4. （路径“si”，节点“6”（“6”节点中的附加信息：4-5,7-8），树的其余部分）
5. 等