Average sizes of suffix trees and DAWGs

AbstractSuffix trees, directed acyclic word graphs (DAWGs) and related data structures are useful for text retrieval and analysis. Linear upper and lower bounds on their sizes are known. Constructing these data structures for random strings, one observes that the size does not increase smoothly, but oscillates between these bounds. We use Mellin transforms to obtain size estimates as integrals of meromorphic functions. Poles on the real axis lead to exact formulae for the average sizes, while poles with nonzero imaginary part lead to very good estimates of the oscillations