Rotation and Queries

Subtask 1:

You can use bruteforce.

Acceptable Complexity: O($n^3$)

Subtask 2:

You can generate each of the rotations and sort them beforehand. If you analyze, you will find the fact that, $i^{th}$ rotation has all of the suffixes of length X of input string as substring, where X = (Length of the input string - i). With this, you can work on each query.

Acceptable Complexity: O($n^2$)

Subtask 3:

Append the whole string excluding the last character of the input string at the end of the input string. Now run the suffix array (Suffix array - Wikipedia) algorithm. You’ll need to store the reverse order of the suffix array where the suffix size is greater than or equal the input string. So, you’ll get an L (where L = size of the input string) sized array which contains the index of rotation (described in the problem statement) lexicographically reversed order (largest suffix comes first). From this reversed suffix array, create an array which will contain the lowest index that has been found so far. Do a binary search on this array to answer each query by using the fact that the $i^{th}$ rotation has all of the suffixes of length X of input string as substring, where X = (Length of the input string - i).

Acceptable Complexity: O($n log_2(n)$)