Solving the String Statistics Problem in Time
Gerth Stølting Brodal
March 2002 |

## Abstract:
The string statistics problem consists of preprocessing a
string of length such that given a query pattern of length , 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
and how it supports queries in time 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 . In this paper we improve the construction time
for the MAST to
by extending the algorithm of Apostolico
and Preparata to exploit properties of efficient joining and splitting of
search trees together with a refined analysis
Available as |

Last modified: 2003-06-08 by webmaster.