Finding Maximal Quasiperiodicities in Strings

Gerth Stølting Brodal
Christian N. S. Pedersen

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 \log^2 n)$. In this paper we give an algorithm that finds all maximal quasiperiodic substrings in a string of length $n$ in time $O(n\log 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

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.