1
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot, that was very helpful $\endgroup$ – George Verouchis May 5 at 7:06

Your Answer

George Verouchis is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.