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(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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. M. Adel’son-Vel’skii and Y. M. Landis. An algorithm for the organization of information. Doklady Akademii Nauk SSSR, 146:263–266, 1962. English translation in Soviet Math. Dokl., 3:1259–1262.
A. V. Aho, J. E. Hopcraft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachusetts, 1974.
A. Apostolico and D. Breslauer. Of periods, quasiperiods, repetitions and covers. In A selection of essays in honor of A. Ehrenfeucht, volume 1261 of Lecture Notes in Computer Science. Springer, 1997.
A. Apostolico and A. Ehrenfeucht. Efficient detection of quasiperiodicities in strings. Theoretical Computer Science, 119:247–265, 1993.
A. Apostolico, M. Farach, and C. S. Iliopoulos. Optimal superprimitivity testing for strings. Information Processing Letters, 39:17–20, 1991.
A. Apostolico and F. P. Preparata. Optimal off-line detection of repetitions in a string. Theoretical Computer Science, 22:297–315, 1983.
D. Breslauer. An on-line string superprimitivity test. Information Processing Letters, 44:345–347, 1992.
G. S. Brodal, R. B. Lyngsø, C. N. S. Pedersen, and J. Stoye. Finding maximal pairs with bounded gap. In Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 1645 of Lecture Notes in Computer Science, pages 134–149, 1999.
G. S. Brodal and C. N. S. Pedersen. Finding maximal quasiperiodicities in strings. Technical Report RS-99-25, BRICS, September 1999.
M. R. Brown and R. E. Tarjan. A fast merging algorithm. Journal of the ACM, 26(2):211–226, 1979.
M. Crochemore. An optimal algorithm for computing the repetitions in a word. Information Processing Letters, 12(5):244–250, 1981.
M. Crochemore. Transducers and repetitions. Theoretical Computer Science, 45:63–86, 1986.
D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
D. Gusfield and J. Stoye. Linear time algorithms for finding and representing all the tandem repeats in a string. Technical Report CSE-98-4, Department of Computer Science, UC Davis, 1998.
C. S. Iliopoulos and L. Mouchard. Quasiperiodicity: From detection to normal forms. Journal of Automata, Languages and Combinatorics, 4(3):213–228, 1999.
R. Kolpakov and G. Kucherov. Maximal repetitions in words or how to find all squares in linear time. Technical Report 98-R-227, LORIA, 1998.
M. G. Main and R. J. Lorentz. An O(n log n) algorithm for finding all repetitions in a string. Journal of Algorithms, 5:422–432, 1984.
M. G. Main and R. J. Lorentz. Linear time recognition of squarefree strings. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume F12 of NATO ASI Series, pages 271–278. Springer, Berlin, 1985.
E. M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, 23(2):262–272, 1976.
K. Mehlhorn. Sorting and Searching, volume 1 of Data Structures and Algorithms. Springer-Verlag, 1994.
Mehlhorn and S. Näher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999.
D. Moore and W. F. Smyth. Computing the covers of a string in linear time. In Proceedings of the 5th Annual Symposium on Discrete Algorithms (SODA), pages 511–515, 1994.
M. Rabin. Discovering repetitions in strings. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume F12 of NATO ASI Series, pages 279–288. Springer, Berlin, 1985.
J. Stoye and D. Gusfield. Simple and flexible detection of contiguous repeats using a suffix tree. In Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 1448 of Lecture Notes in Computer Science, pages 140–152, 1998.
A. Thue. Uber unendliche Zeichenreihen. Skrifter udgivet af Videnskabsselskabet i Christiania, Mathematiskog Naturvidenskabeligklasse, 7:1–22, 1906.
A. Thue. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Skrifter udgivet af Videnskabsselskabet i Christiania, Mathematiskog Naturvidenskabeligklasse, 1:1–67, 1912.
E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14:249–260, 1995.
P. Weiner. Linear pattern matching algorithms. In Proceedings of the 14th Symposium on Switching and Automata Theory, pages 1–11, 1973.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brodal, G.S., Pedersen, C.N.S. (2000). Finding Maximal Quasiperiodicities in Strings. In: Giancarlo, R., Sankoff, D. (eds) Combinatorial Pattern Matching. CPM 2000. Lecture Notes in Computer Science, vol 1848. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45123-4_33
Download citation
DOI: https://doi.org/10.1007/3-540-45123-4_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67633-1
Online ISBN: 978-3-540-45123-5
eBook Packages: Springer Book Archive