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.

Authors

• Amihood Amir
• Gad M. Landau
• Shoshana Marcus
• Dina Sokol

Keywords

• Pattern matching algorithms
• Repetitions
• Periodicity
• Two-dimensional