Editorial for COCI '21 Contest 3 #1 Lampice
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 times in a row. The simplest way to do this is to iterate over all continuous subarrays and check if it repeats
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
and
the left and right end of the subarray, respectively. The length of the current subarray (denote it by
) is then equal to
. In order to check whether it repeats
times, we must check whether the following
subarrays of length
are the same as the initial subarray (from
to
), that is whether
is the same as
. 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
to
).
Comments