MINMOVE - Minimum Rotations
Given a string S[1..n] . A rotation on S is that we move the first character to the right-most of the string. More specific, after a rotation, S becomes T = S[2..n] + S.
For example: S = abcaa, then after a rotation we have S = bcaaa.
Find the minimum number of rotations to make S become the smallest lexicographical order string.
A single line contains a string S. S contains only small letters of English alphabet (‘a’ .. ‘z’), and the length of S is not more than 100000.
A single line contains an integer which represents the minimum number of rotations.
Input: mississippi Output: 10
Test cases and time limit have been updated. Some accepted solution got TLE.
Everyone if you haven't tried O(n) solution, please try that. As @VinyelEm mentioned, there exists a very elegant solution for this in O(n) time.
Time limit exceed..even in O(n)..????
Ritesh Kumar Gupta:
Agree With ~neo~ .Even My DC3 Algorithm Failed to pass the Judge. Same problem http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=756 with almost same constraints passed the ACM Live archieve judge and just took 0.24 seconds ,so is SPOJ really slow?Last edit: 2012-07-01 03:19:27
Using suffix array like idea. Sorts S[i..n]+S[1..] instead of suffixes. O(n*logn*logn) suffix array generation is timing out. So, probably O(n*logn) algorithm must be used.