Finding Maximal Quasiperiodicities in Strings

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

In Proc. 11th Annual Symposium on Combinatorial Pattern Matching, volume 1848 of Lecture Notes in Computer Science, pages 397-411. Springer Verlag, Berlin, 2000.

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

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

Online version

cpm00.pdf (249 Kb)

DOI

10.1007/3-540-45123-4_33

Links

BIBTEX entry

@incollection{cpm00,
  author = "Gerth St{\o}lting Brodal and Christian N{\o}rgaard Storm Pedersen",
  booktitle = "Proc. 11th Annual Symposium on Combinatorial Pattern Matching",
  doi = "10.1007/3-540-45123-4_33",
  isbn = "978-3-540-67633-1",
  pages = "397-411",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Finding Maximal Quasiperiodicities in Strings",
  volume = "1848",
  year = "2000"
}

Other versions