What makes suffix trees so useful as a data structure? Surprisingly, much of their utility and flexibility can be attributed purely to two facts: they keep the suffixes sorted, and they expose the branching words in the string. By representing this information in a different way, we can get much of the benefit of suffix trees without the huge space cost.
Readings
- Udi Manber and Gene Myers. Suffix Arrays: A New Method for On-Line String Searches
- Toru Kasai et al. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications
Links