Two-dimensional maximal repetitions.

Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number of maximal 2D repetitions that can occur in an n × n array. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions. The algorithm is efficient and straightforward, with runtime O (n 2 log ⁡ n + ρ) , where n 2 is the size of the input array and ρ is the number of maximal 2D repetitions in the output. [ABSTRACT FROM AUTHOR]