Charalampopoulos, Panagiotis ;
Radoszewski, Jakub ;
Rytter, Wojciech ;
Waleń, Tomasz ;
Zuba, Wiktor
The Number of Repetitions in 2DStrings
Abstract
The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to twodimensional strings. We consider two types of repetitions in 2Dstrings: 2Druns and quartics (quartics are a 2Dversion of squares in standard strings). Amir et al. introduced 2Druns, showed that there are 𝒪(n³) of them in an n × n 2Dstring 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 2Druns in an n × n 2Dstring is 𝒪(n² log² n). In particular, our bound implies that the 𝒪(n²log n + output) runtime of the algorithm of Amir et al. for computing 2Druns is also 𝒪(n² log² n). We expect this result to allow for exploiting 2Druns algorithmically in the area of 2D pattern matching.
A quartic is a 2Dstring composed of 2 × 2 identical blocks (2Dstrings) 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 1Dstrings. Apostolico and Brimkov showed that there are 𝒪(n² log² n) occurrences of primitively rooted quartics in an n × n 2Dstring 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 1Dstring, that was initiated by Fraenkel and Simpson (Journal of Combinatorial Theory, Series A, 1998), to two dimensions.
Finally, we show some algorithmic applications of 2Druns. 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 quasilinear 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 1Dstrings using runs (Crochemore et al., Theoretical Computer Science, 2014). However, the methods used in 2D are different because of different properties of 2Druns and quartics.
BibTeX  Entry
@InProceedings{charalampopoulos_et_al:LIPIcs:2020:12898,
author = {Panagiotis Charalampopoulos and Jakub Radoszewski and Wojciech Rytter and Tomasz Waleń and Wiktor Zuba},
title = {{The Number of Repetitions in 2DStrings}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {32:132:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12898},
URN = {urn:nbn:de:0030drops128987},
doi = {10.4230/LIPIcs.ESA.2020.32},
annote = {Keywords: 2Drun, quartic, run, square}
}
26.08.2020
Keywords: 

2Drun, quartic, run, square 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 