Searching for a pattern
Chang & Lawler: to search for pattern P in text T, build suffix tree for P and compare T to it
- follow path by symbols of T
- use suffix links when a symbol can’t be matched
- rescan to find what we’ve already seen, then continue
- report a match when we hit the last symbol of P
For suffix trees - slight difference
- when we hit a mismatch, we may need to go back up to a parent node to find the right suffix link to follow
with appropriate optimizations,
O(|T| log(| ? |+|S |)) time