MINMOVE  Minimum Rotations
English  Vietnamese 
Given a string S[1..n] . A rotation on S is that we move the first character to the rightmost of the string. More specific, after a rotation, S becomes T = S[2..n] + S[1].
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.
Input
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.
Output
A single line contains an integer which represents the minimum number of rotations.
Example
Input: mississippi Output: 10
Test cases and time limit have been updated. Some accepted solution got TLE.
hide comments
ahemanthkumar:
20150923 23:02:42
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.


aksam:
20150605 12:44:41
n*logn*logn >TLE


Sourav Maji:
20150311 20:45:24
Time limit exceed..even in O(n)..???? 

Ritesh Kumar Gupta:
20120701 03:18:18
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: 20120701 03:19:27 

VinyleEm:
20101226 19:52:03
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.

Added by:  Race with time 
Date:  20081229 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO PERL6 
Resource:  Based on a problem from ACM Central European Programming Contest 