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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
Most ,
, or
methods should pass, including suffix array and suffix automaton. The simplest solution is to find the hash of every cyclic shift of
and store them in a set, then hash each
length substring of
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