Rotation and Queries

You will be given a string S consisting of lowercase English characters and N queries. In each query, you have to find the lexicographically largest string rotation that has a suffix of the original string with a length of X as a substring. For example: In given sample, bca string has 3 rotations, bca (0th0^{th}0th rotation), cab (1st1^{st}1st rotation), abc (2nd2^{nd}2nd rotation) respectively. Among these rotations, there are two rotations that have ca (a suffix of the original string with a length of 2) as substring. Between these two rotations, the later one is lexicographically larger. So, the answer to the second query ( query with X = 2) of the first testcase of the sample i/o is 1 (index of rotation).


This is a companion discussion topic for the original entry at https://toph.co/p/untitled