nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Shortest Covers of All Cyclic Shifts of a String

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

Erschienen in: WALCOM: Algorithms and Computation

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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)\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips

Nächstes Kapitel 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)

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

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"