Document Open Access Logo

Two-Dimensional Maximal Repetitions

Authors Amihood Amir, Gad M. Landau, Shoshana Marcus, Dina Sokol

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2018.2.pdf
  • Filesize: 483 kB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics on words
  • Theory of computation → Design and analysis of algorithms
Keywords
  • pattern matching algorithms
  • repetitions
  • periodicity
  • two-dimensional

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number of maximal 2D repetitions that can occur in a matrix. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions in a matrix. The algorithm is efficient and straightforward, with runtime O(n^2 log n log log n+ rho log n), where n^2 is the size of the input, and rho is the number of 2D repetitions in the output.

Cite As Get BibTex

Amihood Amir, Gad M. Landau, Shoshana Marcus, and Dina Sokol. Two-Dimensional Maximal Repetitions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.2

Author Details

Amihood Amir
  • Bar Ilan University, Ramat-Gan, 52900, Israel
Gad M. Landau
  • University of Haifa, Haifa 31905, Israel, and, NYU Tandon School of Engineering, New York University, Six MetroTech Center, Brooklyn, NY 11201, USA
Shoshana Marcus
  • Kingsborough Community College of the City University of New York, 2001 Oriental Boulevard, Brooklyn, NY 11235, USA
Dina Sokol
  • Brooklyn College of the City University of New York, 2900 Bedford Avenue, Brooklyn, NY, 11210, USA

Funding

  • Amir, Amihood: Partially supported by the Israel Science Foundation grant 571/14 and Grant No. 2014028 from the United States-Israel Binational Science Foundation (BSF).
  • Landau, Gad M.: Partially supported by the Israel Science Foundation grant 571/14 and Grant No. 2014028 from the United States-Israel Binational Science Foundation (BSF).
  • Sokol, Dina: Partially supported by Grant No. 2014028 from the United States-Israel Binational Science Foundation (BSF).

References

  1. A. Amir and G. Benson. Two-dimensional periodicity in rectangular arrays. SIAM J. Comput., 27(1):90-106, 1998. URL: http://dx.doi.org/10.1137/S0097539795298321.
  2. A. Amir, G. M. Landau, M. Lewenstein, and D. Sokol. Dynamic text and static pattern matching. ACM Trans. Algorithms, 3(2):19, 2007. URL: http://dx.doi.org/10.1145/1240233.1240242.
  3. A. Apostolico and V. E. Brimkov. Fibonacci arrays and their two-dimensional repetitions. Theor. Comput. Sci., 237(1-2):263-273, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(98)00182-0.
  4. A. Apostolico and V. E. Brimkov. Optimal discovery of repetitions in 2d. Discrete Applied Mathematics, 151(1-3):5-20, 2005. URL: http://dx.doi.org/10.1016/j.dam.2005.02.019.
  5. N. Bacquey. Primitive roots of bi-periodic infinite pictures. In Words 2015, 2015. Google Scholar
  6. H. Bannai, T. I, S. Inenaga, Y. Nakashima, M. Takeda, and K. Tsuruta. A new characterization of maximal repetitions by Lyndon trees. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 562-571, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.38.
  7. H. Bannai, T. I, S. Inenaga, Y. Nakashima, M. Takeda, and K. Tsuruta. The "runs" theorem. SIAM J. Comput., 46(5):1501-1514, 2017. URL: http://dx.doi.org/10.1137/15M1011032.
  8. M. Crochemore, L. Gasieniec, R. Hariharan, S. Muthukrishnan, and W. Rytter. A constant time optimal parallel algorithm for two-dimensional pattern matching. SIAM J. Comput., 27(3):668-681, 1998. URL: http://dx.doi.org/10.1137/S0097539795280068.
  9. M. Crochemore, L. Ilie, and W. Rytter. Repetitions in strings: Algorithms and combinatorics. Theor. Comput. Sci., 410(50):5227-5235, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.08.024.
  10. M. Crochemore and W. Rytter. Sqares, cubes, and time-space efficient string searching. Algorithmica, 13(5):405-425, 1995. URL: http://dx.doi.org/10.1007/BF01190846.
  11. G. Gamard and G. Richomme. Coverability in two dimensions. In A. H. Dediu, E. Formenti, C. Martín-Vide, and B. Truthe, editors, Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, volume 8977 of Lecture Notes in Computer Science, pages 402-413. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-15579-1_31.
  12. G. Gamard, G. Richomme, J. Shallit, and T. J. Smith. Periodicity in rectangular arrays. Inf. Process. Lett., 118:58-63, 2017. URL: http://dx.doi.org/10.1016/j.ipl.2016.09.011.
  13. D. Gusfield and J. Stoye. Linear time algorithms for finding and representing all the tandem repeats in a string. J. Comput. Syst. Sci., 69(4):525-546, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2004.03.004.
  14. R. M. Karp, R. E. Miller, and A. L. Rosenberg. Rapid identification of repeated patterns in strings, trees and arrays. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing, May 1-3, 1972, Denver, Colorado, USA, pages 125-136, 1972. URL: http://dx.doi.org/10.1145/800152.804905.
  15. T. Kociumaka, J. Radoszewski, W. Rytter, and T. Walen. Internal pattern matching queries in a text and applications. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 532-551, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.36.
  16. R. M. Kolpakov and G. Kucherov. Finding maximal repetitions in a word in linear time. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 596-604. IEEE Computer Society, 1999. URL: http://dx.doi.org/10.1109/SFFCS.1999.814634.
  17. S. Marcus and D. Sokol. 2d Lyndon words and applications. Algorithmica, 77(1):116-133, 2017. URL: http://dx.doi.org/10.1007/s00453-015-0065-z.
  18. E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249-260, 1995. URL: http://dx.doi.org/10.1007/BF01206331.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »