Top

Published in:

2020 | OriginalPaper | Chapter

Shortest Covers of All Cyclic Shifts of a String

Authors : Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A factor W of a string X is called a cover of X, if X can be constructed by concatenations and superpositions of W. Breslauer (IPL, 1992) proposed a well-known \(\mathcal {O}(n)\)-time algorithm that computes the shortest cover of every prefix of a string of length n. We show an \(\mathcal {O}(n \log n)\)-time algorithm that computes the shortest cover of every cyclic shift of a string and an \(\mathcal {O}(n)\)-time algorithm that computes the shortest among these covers. A related problem is the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is \(\varOmega (\log n)\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips

next chapter Packing Trees into 1-Planar Graphs

Apostolico, A., Farach, M., Iliopoulos, C.S.: Optimal superprimitivity testing for strings. Inf. Process. Lett. 39(1), 17–20 (1991). https://doi.org/10.1016/0020-0190(91)90056-NMathSciNetCrossRefMATH

Apostolico, A., Preparata, F.P.: Data structures and algorithms for the string statistics problem. Algorithmica 15(5), 481–494 (1996). https://doi.org/10.1007/BF01955046MathSciNetCrossRefMATH

Bannai, H., Tomohiro, I., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The “runs” theorem. SIAM J. Comput. 46(5), 1501–1514 (2017). https://doi.org/10.1137/15M1011032MathSciNetCrossRefMATH

Breslauer, D.: An on-line string superprimitivity test. Inf. Process. Lett. 44(6), 345–347 (1992). https://doi.org/10.1016/0020-0190(92)90111-8MathSciNetCrossRefMATH

Christou, M., Crochemore, M., Guth, O., Iliopoulos, C.S., Pissis, S.P.: On left and right seeds of a string. J. Discrete Algorithms 17, 31–44 (2012). https://doi.org/10.1016/j.jda.2012.10.004MathSciNetCrossRefMATH

Christou, M., et al.: Efficient seed computation revisited. Theor. Comput. Sci. 483, 171–181 (2013). https://doi.org/10.1016/j.tcs.2011.12.078MathSciNetCrossRefMATH

Crochemore, M., Iliopoulos, C.S., Kubica, M., Radoszewski, J., Rytter, W., Waleń, T.: Extracting powers and periods in a word from its runs structure. Theor. Comput. Sci. 521, 29–41 (2014). https://doi.org/10.1016/j.tcs.2013.11.018MathSciNetCrossRefMATH

Crochemore, M., Rytter, W.: Squares, cubes, and time-space efficient string searching. Algorithmica 13(5), 405–425 (1995). https://doi.org/10.1007/BF01190846MathSciNetCrossRefMATH

Deza, A., Franek, F., Thierry, A.: How many double squares can a string contain? Discrete Appl. Math. 180, 52–69 (2015). https://doi.org/10.1016/j.dam.2014.08.016MathSciNetCrossRefMATH

10.

Farach, M.: Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, 19–22 October 1997, pp. 137–143. IEEE Computer Society (1997). https://doi.org/10.1109/SFCS.1997.646102

11.

Fraenkel, A.S., Simpson, J.: How many squares can a string contain? J. Comb. Theory Ser. A 82(1), 112–120 (1998). https://doi.org/10.1006/jcta.1997.2843MathSciNetCrossRefMATH

12.

Gusfield, D., Stoye, J.: Linear time algorithms for finding and representing all the tandem repeats in a string. J. Comput. Syst. Sci. 69(4), 525–546 (2004). https://doi.org/10.1016/j.jcss.2004.03.004MathSciNetCrossRefMATH

13.

Iliopoulos, C.S., Moore, D.W.G., Park, K.: Covering a string. Algorithmica 16(3), 288–297 (1996). https://doi.org/10.1007/BF01955677MathSciNetCrossRefMATH

14.

Iliopoulos, C.S., Moore, D.W.G., Smyth, W.F.: A characterization of the squares in a Fibonacci string. Theor. Comput. Sci. 172(1–2), 281–291 (1997). https://doi.org/10.1016/S0304-3975(96)00141-7MathSciNetCrossRefMATH

15.

Iliopoulos, C.S., Moore, D.W.G., Smyth, W.F.: The covers of a circular Fibonacci string. J. Comb. Math. Comb. Comput. 26, 227–236 (1998)MathSciNetMATH

16.

Kociumaka, T., Kubica, M., Radoszewski, J., Rytter, W., Waleń, T.: A linear time algorithm for seeds computation. In: Rabani, Y. (ed.) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 17–19 January 2012, pp. 1095–1112. SIAM (2012). https://doi.org/10.1137/1.9781611973099.86

17.

Kociumaka, T., Kubica, M., Radoszewski, J., Rytter, W., Waleń, T.: A linear time algorithm for seeds computation. CoRR abs/1107.2422v2 (2019). http://arxiv.org/abs/1107.2422v2

18.

Kociumaka, T., Radoszewski, J., Rytter, W., Waleń, T.: Internal pattern matching queries in a text and applications. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4–6 January 2015, pp. 532–551. SIAM (2015). https://doi.org/10.1137/1.9781611973730.36

19.

Li, Y., Smyth, W.F.: Computing the cover array in linear time. Algorithmica 32(1), 95–106 (2002). https://doi.org/10.1007/s00453-001-0062-2MathSciNetCrossRefMATH

20.

Moore, D.W.G., Smyth, W.F.: An optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 50(5), 239–246 (1994). https://doi.org/10.1016/0020-0190(94)00045-XMathSciNetCrossRefMATH

21.

Moore, D.W.G., Smyth, W.F.: A correction to “an optimal algorithm to compute all the covers of a string”. Inf. Process. Lett. 54(2), 101–103 (1995). https://doi.org/10.1016/0020-0190(94)00235-QCrossRef

22.

Séébold, P.: Propriétés combinatoires des mots infinis engendrés par certains morphismes. Report no. 85-16, LITP, Paris (1985)

Title: Shortest Covers of All Cyclic Shifts of a String
Authors: Maxime Crochemore
Costas S. Iliopoulos
Jakub Radoszewski
Wojciech Rytter
Juliusz Straszyński
Tomasz Waleń
Wiktor Zuba
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner