2026-07-23T15:20:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16150 2024-03-06T10:56:42Z ddc:004 open_access

Rectangular Tile Covers of 2D-Strings Radoszewski, Jakub Rytter, Wojciech Straszyński, Juliusz Waleń, Tomasz Zuba, Wiktor tile cover periodicity efficient algorithm We consider tile covers of 2D-strings which are a generalization of periodicity of 1D-strings. We say that a 2D-string A is a tile cover of a 2D-string S if S can be decomposed into non-overlapping 2D-strings, each of them equal to A or to A^T, where A^T is the transpose of A. We show that all tile covers of a 2D-string of size N can be computed in 𝒪(N^{1+ε}) time for any ε > 0. We also show a linear-time algorithm for computing all 1D-strings being tile covers of a 2D-string. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Radoszewski and Wojciech Rytter and Juliusz Straszyński and Tomasz Waleń and Wiktor Zuba 2022 Is Part Of LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2022.23 urn:nbn:de:0030-drops-161508 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.23 eng https://creativecommons.org/licenses/by/4.0/legalcode