MINMOVE - Minimum Rotations

no tags 

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.


hide comments
eightnoteight: 2015-12-19 13:58:13

got ac using optimized n*logn*logn suffix arrays.

ahemanthkumar: 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.

aksam: 2015-06-05 12:44:41

n*logn*logn ---->TLE
n*logn -----> AC

Sourav Maji: 2015-03-11 20:45:24

Time limit exceed..even in O(n)..????

Ritesh Kumar Gupta: 2012-07-01 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: 2012-07-01 03:19:27
VinyleEm: 2010-12-26 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.

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

Last edit: 2010-12-27 00:56:43

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