2026-07-22T06:36:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9465 2024-03-06T10:43:48Z ddc:004 open_access

Two-Dimensional Maximal Repetitions Amir, Amihood Landau, Gad M. Marcus, Shoshana Sokol, Dina pattern matching algorithms repetitions periodicity two-dimensional 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amihood Amir and Gad M. Landau and Shoshana Marcus and Dina Sokol 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.2 urn:nbn:de:0030-drops-94652 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.2 eng https://creativecommons.org/licenses/by/3.0/legalcode