Rectangular tile covers of 2D-strings
Presented at the 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 (June 2022), Prague, Czech Republic
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|
|Organisation||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 Annual Symposium on Combinatorial Pattern Matching (pp. 23:1–23:14). doi:10.4230/LIPIcs.CPM.2022.23