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 次计数。