Aarhus University Seal

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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
  • Bioinformatics Research Centre (BiRC)
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 (nlog2 n) and how it supports queries in time (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 (n). In this paper we improve the construction time for the MAST to (nlogn) by extending the algorithm of Apostolico and Preparata to exploit properties of efficient joining and splitting of search trees together with a refined analysis. Partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Supported by the Carlsberg Foundation (contract number ANS-0257/20).Basic Research in Computer Science (BRICS), www.brics.dk, funded by the Danish National Research Foundation.Bioinformatics Research Center (BiRC), www.birc.dk, funded by Aarhus University Research Fundation.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming : 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings
EditorsPeter Widmayer, Stephan Eidenbenz, Francisco Triguero, Rafael Morales, Ricardo Conejo, Matthew Hennessy
Number of pages12
Publication year2002
ISBN (print)978-3-540-43864-5
Publication statusPublished - 2002
Event29th International Colloquium, ICALP 2002 - Málaga, Spain
Duration: 8 Jul 200213 Jul 2002
Conference number: 29


Conference29th International Colloquium, ICALP 2002
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 280814