Editorial for COCI '15 Contest 5 #2 Multigram

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.

Let there be given a string of length $N$ $N$ .

We can iterate over all divisors $K$ $K$ of number $N$ $N$ and check whether it's possible for a string to consist of anagrams of length $K$ $K$ .

In order to check this, we need to determine whether the substrings $[1, K], [K+1, 2K], \dots, [N-K+1, N]$ $[1, K], [K + 1, 2 K], \dots, [N - K + 1, N]$ are mutually anagrams.

It is sufficient to sort all these strings and check if they're equal then.

Comments

There are no comments at the moment.