The string statistics problem consists of preprocessing a
string of length
![$n$](Abs/img2.gif)
such that given a query pattern of length
![$m$](Abs/img3.gif)
, the
maximum number of non-overlapping occurrences of the query pattern in the
string can be reported efficiently. Apostolico and Preparata introduced the
minimal augmented suffix tree (MAST) as a data structure for the string
statistics problem, and showed how to construct the MAST in time
![${\cal
O}(n\log^2 n)$](Abs/img4.gif)
and how it supports queries in time
![${\cal O}(m)$](Abs/img5.gif)
for constant
sized alphabets. A subsequent theorem by Fraenkel and Simpson stating that a
string has at most a linear number of distinct squares implies that the MAST
requires space
![${\cal O}(n)$](Abs/img6.gif)
. In this paper we improve the construction time
for the MAST to
![${\cal O}(n\log n)$](Abs/img7.gif)
by extending the algorithm of Apostolico
and Preparata to exploit properties of efficient joining and splitting of
search trees together with a refined analysis