Editorial for COCI '21 Contest 3 #1 Lampice


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The problem asks to find a continuous subarray (that is pattern) which repeats k times in a row. The simplest way to do this is to iterate over all continuous subarrays and check if it repeats k times in a row. We can iterate over these subarrays using two nested for loops, one going over all possible left ends of the subarray, and one going over all right ends. Denote by l and r the left and right end of the subarray, respectively. The length of the current subarray (denote it by d) is then equal to r-l+1. In order to check whether it repeats k times, we must check whether the following k-1 subarrays of length d are the same as the initial subarray (from l to r), that is whether [l+d, r+d], [l+2d, r+2d], \dots, [l+(k-1)d, r+(k-1)d] is the same as [l, r]. This is done using two nested for loops, one going over those subarrays and the other checking if they are the same with the initial one (from l to r).


Comments

There are no comments at the moment.