The Prague Stringology Conference 2005

Elise Prieur-Gaston and Thierry Lecroq

From Suffix Trees to Suffix Vectors

We present a first formal setting for suffix vectors that are space economical alternative data structures to suffix trees. We give two linear algorithms for converting a suffix tree into a suffix vector and conversely. We enrich suffix vectors with formulas for counting the number of occurrences of repeated substrings. We also propose an alternative implementation for suffix vectors that should outperform the existing one.

Download article: Article in PostScript Article in PDF
 PostScript   PDF