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), \mathcal O(n \log n), or \mathcal 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 and store them in a set, then hash each |S| length substring of 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.