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
inkretbear:
20180823 23:15:18
Was getting WA on #17 with prefix hash


hamjosh1:
20160930 13:29:49
learned a lot :D 

vsp4:
20160911 19:19:06
Those who are using stl, make sure to use stable_sort if using nlogn*logn solution. Costed me few WA 

minhthai:
20160403 05:42:51
"Some accepted solution got TLE."


lakshay_v06:
20160205 15:33:28
Same as http://www.spoj.com/problems/BEADS/ . O(nlogn) passed. :) 

Dhawal Harkawat:
20160122 05:30:20
silly mistake costed two WAs at #10. finally AC. 

Sumit Vohra:
20160121 23:37:21
solved using suffix automaton in O(n)


eightnoteight:
20151219 13:58:13
got ac using optimized n*logn*logn suffix arrays. 

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

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 