ROTSTRNG - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

We are given a string S and we keep rotating it till we get back to the string S. Note that this can always be possible, if we rotate S a multiple of N times, where N is the length of S. But, we are more concerned if it can be reached before that. Let S(i) = S[i…N-1] + S[1…i-1]. So S(0) = S. Once we know for each i, if S(i) equals S, then we can simulate the rotations of Monkey and Po, as any rotation will result in a string which is one of S(i). We can use KMP here :). Consider a string S2 = S + S and find the KMP Failure Function F for S2. F[i] denotes the length of the maximum proper-suffix that is also prefix of S2.

If F[i] = N, then N length suffix of S2[0,…,i], i.e., S2[i-N+1,…,i] = N length prefix of S2[0,…,i] = S2[0…N-1] = S. So, we can find all such indices using O(n) KMP and then just simulate the rotations by just going through the S(i)s in order. Note that answer will always exist and there is never a -1 case.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

4 Likes

i m not able to understand what you make the use of KMP-failure function …can u plz help me out …i don’t want the code but the description that how u use it

//