Editorial for CCC '20 J4 - Cyclic Shifts (Hard) - Olympiads Online Judge

Editorial for CCC '20 J4 - Cyclic Shifts (Hard)

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.

Subtask 1

Most $\mathcal O(n)$ $O (n)$ , $\mathcal O(n \log n)$ $O (n \log n)$ , or $\mathcal O(n \log^2 n)$ $O (n \log^{2} n)$ methods should pass, including suffix array and suffix automaton. The simplest solution is to find the hash of every cyclic shift of $S$ $S$ and store them in a set, then hash each $|S|$ $| S |$ length substring of $T$ $T$ and check if they match any cyclic shift. Note that for this problem you will need to take steps to avoid hash collisions. A lot of hashing solutions receive a WA because they only have a single, 32-bit, or composite modulus or a nonrandomized base.

Full Solution

To solve the problem you will need a fast string matching algorithm with a good constant such as KMP or Z. This is only worth 10% because I don't really like solutions based on constant factors (other than bitset).

Comments

There are no comments at the moment.