THE AVERAGE HIGHT OF THE SUFFI X TREE
Pla Information · 1996
Consider the suffix tree built from the first n suffixes of the infinite string X=X1X2…,where X1,X2,…are independently and identically uniformly distributed over a finite alphabet ∑.in this paper we present tight upper and lower bonnds on the expectation and variance of the hight of the suffix tree.