algorithm - 是否有众所周知的算法来计算后缀树中的子串？

Question

我已经实现了一种算法来构建后缀树。 现在，我正在尝试实现一个方法计数，它返回查询发生的次数作为引用序列的子列表/子间隔。 最好的方法是什么？

例子:

序列的后缀树

1,2,50,100,25,25,25,50,100,25,25 

查询

25,25

结果

3

Answer 1

一种方法是:

1. 向列表添加一个唯一的终止符号(例如 -1)。

2. 构造后缀树。

3. 现在根据查询中的数字沿着后缀树向下走。

4. 如果这不可能，则查询出现 0 次。

5. 否则，根据您当前位置计算子树中的叶节点。

查询在字符串中出现的次数等于子树中叶节点的个数。

如果您想进行多个查询，那么您可以使用深度优先搜索来计算 O(n) 中叶节点的数量，并将答案存储在每个节点中。这将让您在时间 O(k) 内执行查询，其中 k 是查询字符串的长度。

这是可行的，因为您的后缀树将具有每个后缀的叶节点:

1,2,50,100,25,25,25,50,100,25,25
2,50,100,25,25,25,50,100,25,25
50,100,25,25,25,50,100,25,25
100,25,25,25,50,100,25,25
25,25,25,50,100,25,25
25,25,50,100,25,25
25,50,100,25,25
50,100,25,25
100,25,25
25,25
25

其中，按照25,25查询下树后，子树中剩余的叶子节点分别对应:

25,25,25,50,100,25,25
25,25,50,100,25,25
25,25

它给出了字符串中查询的 3 次计数。