Solving the String Statistics Problem in Time O(nlog n)

Gerth Stølting Brodal, Rune Bang Lyngsø, Anna Östlin, and Christian Nørgaard Storm Pedersen

In Proc. 29th International Colloquium on Automata, Languages, and Programming, volume 2380 of Lecture Notes in Computer Science, pages 728-739. Springer Verlag, Berlin, 2002.

Abstract

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

Copyright notice

© Springer-Verlag Berlin Heidelberg 2002. All rights reserved.

Online version

icalp02string.pdf (166 Kb)

DOI

10.1007/3-540-45465-9_62

Links

BIBTEX entry

@incollection{icalp02,
  author = "Gerth St{\o}lting Brodal and Rune Bang Lyngs{\o} and Anna \"Ostlin and Christian N{\o}rgaard Storm Pedersen",
  booktitle = "Proc. 29th International Colloquium on Automata, Languages, and Programming",
  doi = "10.1007/3-540-45465-9_62",
  isbn = "978-3-540-43864-9",
  pages = "728-739",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Solving the String Statistics Problem in Time $O(n\log n)$",
  volume = "2380",
  year = "2002"
}

Other versions