后缀树检查 k 位置之前是否存在 P 模式
Suffix Tree check existence of P pattern before k position
我需要设计一个算法，给定一个 T 长度为 n 的字符串，经过一个过程 O(n)，对于每个m 长度的字符串 P 和一个介于 1 到 n 之间的 k 值，以检查 O(m)的时候，如果P在k位置之前出现在T上，只使用Suffix Tree.
不幸的是，没有任何好的生物信息学书籍包含公平的例子和实用的方法。 Dan Gusfield 的书没有提供解决方案手册。
预处理：构建后缀树后，使用DFS对每个节点标记其后代中出现的后缀的最小索引。
查询：在P所指的链接上在后缀树中下降，阈值上面构造的节点值。
我需要设计一个算法，给定一个 T 长度为 n 的字符串，经过一个过程 O(n)，对于每个m 长度的字符串 P 和一个介于 1 到 n 之间的 k 值，以检查 O(m)的时候，如果P在k位置之前出现在T上，只使用Suffix Tree.
不幸的是，没有任何好的生物信息学书籍包含公平的例子和实用的方法。 Dan Gusfield 的书没有提供解决方案手册。
预处理：构建后缀树后，使用DFS对每个节点标记其后代中出现的后缀的最小索引。
查询：在P所指的链接上在后缀树中下降，阈值上面构造的节点值。