论文标题
2D弦中的重复数量
The Number of Repetitions in 2D-Strings
论文作者
论文摘要
周期性和重复的概念在字符串中，因此它们的奔跑和正方形自然延伸到二维字符串。我们考虑2D串中的两种重复类型：2D-run和四弦（四分之一是标准字符串中正方形的2D）。 Amir等。引入了2D运行，表明其中有$ o（n^3）$中的$ n \ times n $ 2D弦，并提出了一个简单的结构，给出了$ω（n^2）$的下限（n^2）$（TCS 2020）。我们通过证明$ n \ times n $ 2D弦的2D跑数为$ O（n^2 \ log^2 n）$，迈出了关闭这些边界之间差距的重要一步。特别是，我们的约束意味着$ O（n^2 \ log n + \ textsf {output}）$ amir等人算法的运行时间。用于计算2D运行也是$ O（n^2 \ log^2 n）$。我们希望该结果允许在2D模式匹配的区域中以算法利用2D-RUN。 四分之一是由Apostolico和Brimkov（TCS 2000）介绍的2D弦，由$ 2 \ times 2 $相同的块（2D-弦）组成（TCS 2000），在四分之一的情况下，它们仅意味着原始根源的四分之一，即由Primitive Block构建。在这里，我们的四分之一概念更笼统，并且类似于1D串中的正方形的概念。 Apostolico和Brimkov表明，有$ O（N^2 \ log^2 N）$在$ n \ times n $ 2D弦中出现原始植根的四分之一，并且可以实现这种界限。因此，不同原始植根的四分之一的数量为$ O（n^2 \ log^2 n）$。在这里，我们证明了不同的通用四分之一的数量也为$ O（n^2 \ log^2 n）$。这将一弦中不同正方形数量的丰富组合研究扩展到了Fraenkel和Simpson（J.Comb。TheolopeA 1998）引发的，并将其扩展到两个维度。 最后，我们显示了一些2D运行的算法应用。 （由于ARXIV要求而缩短了摘要。）
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 $O(n^3)$ of them in an $n \times n$ 2D-string and presented a simple construction giving a lower bound of $Ω(n^2)$ for their number (TCS 2020). We make a significant step towards closing the gap between these bounds by showing that the number of 2D-runs in an $n \times n$ 2D-string is $O(n^2 \log^2 n)$. In particular, our bound implies that the $O(n^2\log n + \textsf{output})$ run-time of the algorithm of Amir et al. for computing 2D-runs is also $O(n^2 \log^2 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 \times 2$ identical blocks (2D-strings) that was introduced by Apostolico and Brimkov (TCS 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 $O(n^2 \log^2 n)$ occurrences of primitively rooted quartics in an $n \times n$ 2D-string and that this bound is attainable. Consequently the number of distinct primitively rooted quartics is $O(n^2 \log^2 n)$. Here, we prove that the number of distinct general quartics is also $O(n^2 \log^2 n)$. This extends the rich combinatorial study of the number of distinct squares in a 1D-string, that was initiated by Fraenkel and Simpson (J. Comb. Theory A 1998), to two dimensions. Finally, we show some algorithmic applications of 2D-runs. (Abstract shortened due to arXiv requirements.)
