后缀树检查k位置之前是否存在P模式

Question

我需要设计一个算法，给定一个长度为n的T字符串，在一个过程O(n(之后，对于每个长度为m的字符串p和一个介于1到n之间的>k值，如果p出现在T上k位置之前时，只使用后缀树来检查O(m(time。

不幸的是，没有任何好的生物信息学书籍有公平的例子和实用的方法。Dan Gusfield的书并没有提供解决方案手册。

Answer 1

预处理：构建后缀树后，使用DFS为每个节点标记其子代中出现的后缀的最小索引。

查询：在p指示的链接上的后缀树中下降，阈值上面构造的节点值。