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[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.


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

hide comments
2015-12-19 13:58:13 eightnoteight
got ac using optimized n*logn*logn suffix arrays.
2015-09-23 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.
2015-06-05 12:44:41 aksam
n*logn*logn ---->TLE
n*logn -----> AC
2015-03-11 20:45:24 Sourav Maji
Time limit exceed..even in O(n)..????
2012-07-01 03:18:18 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
2010-12-26 19:52:03 VinyleEm
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.

Edit: It turns out that there is a beautiful O(n) solution for this problem.

Last edit: 2010-12-27 00:56:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.