2022-06-22
Rectangular tile covers of 2D-strings
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.4230/LIPIcs.CPM.2022.23 | |
| 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. (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 |
|
