Given a string str[1...n], a pattern pat[1...m], and a suffix tree constructed for str, the occurrences of pat in str can be found by traversing the suffix tree as follows:
- Begin at the root node and iteratively consume characters from
patby matching them against edge labels in the tree. - If all characters of
patare successfully matched, proceed to the node at which the pattern ends and traverse the subtree rooted at that node to collect all leaf nodes. - Each leaf node represents a suffix of
strand stores the starting index of that suffix; the set of these indices corresponds to all positions instrwherepatoccurs.