文章基本信息

标题：The Number of Repetitions in 2D-Strings
本地全文：下载
作者：Panagiotis Charalampopoulos ; Jakub Radoszewski ; Wojciech Rytter 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：32:1-32:18
DOI：10.4230/LIPIcs.ESA.2020.32
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to two-dimensional strings. We consider two types of repetitions in 2D-strings: 2D-runs and quartics (quartics are a 2D-version of squares in standard strings). Amir et al. introduced 2D-runs, showed that there are ð'ª(nÂ³) of them in an n Ã- n 2D-string and presented a simple construction giving a lower bound of Î©(nÂ²) for their number (Theoretical Computer Science, 2020). We make a significant step towards closing the gap between these bounds by showing that the number of 2D-runs in an n Ã- n 2D-string is ð'ª(nÂ² logÂ² n). In particular, our bound implies that the ð'ª(nÂ²log n + output) run-time of the algorithm of Amir et al. for computing 2D-runs is also ð'ª(nÂ² logÂ² n). We expect this result to allow for exploiting 2D-runs algorithmically in the area of 2D pattern matching. A quartic is a 2D-string composed of 2 Ã- 2 identical blocks (2D-strings) that was introduced by Apostolico and Brimkov (Theoretical Computer Science, 2000), where by quartics they meant only primitively rooted quartics, i.e. built of a primitive block. Here our notion of quartics is more general and analogous to that of squares in 1D-strings. Apostolico and Brimkov showed that there are ð'ª(nÂ² logÂ² n) occurrences of primitively rooted quartics in an n Ã- n 2D-string and that this bound is attainable. Consequently the number of distinct primitively rooted quartics is ð'ª(nÂ² logÂ² n). The straightforward bound for the maximal number of distinct general quartics is ð'ª(nâ´). Here, we prove that the number of distinct general quartics is also ð'ª(nÂ² logÂ² n). This extends the rich combinatorial study of the number of distinct squares in a 1D-string, that was initiated by Fraenkel and Simpson (Journal of Combinatorial Theory, Series A, 1998), to two dimensions. Finally, we show some algorithmic applications of 2D-runs. Specifically, we present algorithms for computing all occurrences of primitively rooted quartics and counting all general distinct quartics in ð'ª(nÂ² logÂ² n) time, which is quasi-linear with respect to the size of the input. The former algorithm is optimal due to the lower bound of Apostolico and Brimkov. The latter can be seen as a continuation of works on enumeration of distinct squares in 1D-strings using runs (Crochemore et al., Theoretical Computer Science, 2014). However, the methods used in 2D are different because of different properties of 2D-runs and quartics.
关键词：2D-run; quartic; run; square