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 AT, where AT is the transpose of A. We show that all tile covers of a 2D-string of size N can be computed in O(N1+ε) time for any ε > 0. We also show a linear-time algorithm for computing all 1D-strings being tile covers of a 2D-string.

, ,
33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Radoszewski, J, Rytter, W, Straszyński, J, Waleń, T, & Zuba, W.P. (2022). Rectangular tile covers of 2D-strings. In Leibniz International Proceedings in Informatics, LIPIcs. doi:10.4230/LIPIcs.CPM.2022.23