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.

, ,
Leibniz International Proceedings in Informatics
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. (2022). Rectangular tile covers of 2D-strings. In Annual Symposium on Combinatorial Pattern Matching (pp. 23:1–23:14). doi:10.4230/LIPIcs.CPM.2022.23