Finding Maximal Quasiperiodicities in Strings

Gerth Stølting Brodal and Christian Nørgaard Storm Pedersen

Technical Report, BRICS-RS-99-25, BRICS, Department of Computer Science, Aarhus University, 20 pages, September 1999.

Abstract

Apostolico and Ehrenfeucht defined the notion of a maximal quasiperiodic substring and gave an algorithm that finds all maximal quasiperiodic substrings in a string of length n in time O(n log2 n). In this paper we give an algorithm that finds all maximal quasiperiodic substrings in a string of length n in time O(nlog n) and space O(n). Our algorithm uses the suffix tree as the fundamental data structure combined with efficient methods for merging and performing multiple searches in search trees. Besides finding all maximal quasiperiodic substrings, our algorithm also marks the nodes in the suffix tree that have a superprimitive path-label

Copyright notice

Copyright © 1999, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-99-25.pdf (257 Kb)

BIBTEX entry

@techreport{brics-rs-99-25,
  author = "Gerth St{\o}lting Brodal and Christian N{\o}rgaard Storm Pedersen",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "September",
  number = "BRICS-RS-99-25",
  pages = "20",
  title = "Finding Maximal Quasiperiodicities in Strings",
  year = "1999"
}