# Checking the existence of a pattern in a given prefix

I need to design an algorithm that given a string $$T$$ of length $$n$$, performs $$O(n)$$ preprocessing, and can then answer queries of the sort "does a string $$P$$ of length $$m$$ appear in $$T$$ before position $$k$$" in time $$O(m)$$. The algorithm should use a suffix tree.

Unfortunately there are not any good bioinformatics books with fair examples and practical methodologies. Dan Gusfield's book does not offer a solution manual.

New contributor
George Verouchis is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Recall that in a suffix tree for $$T$$, each leaf corresponds to a suffix of $$T$$, and is labeled by its position. Furthermore, each internal vertex corresponds to a common prefix of some suffixes of $$T$$. We label each internal vertex with the minimal position of a suffix covered by it.
Construct a suffix tree for $$T$$, and augment it by labeling the internal vertices as described above. Given a pattern $$P$$, traverse the suffix tree to find the vertex corresponding to $$P$$ (it might correspond to some extension of $$P$$), and check whether the minimal position written there implies that $$P$$ occurs before position $$k$$.