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
coolcoder_iith: 2019-10-03 20:19:13

time out at #12
what to do

yaswanth: 2019-09-15 17:47:12

Tried n*logn*logn with quite number of optimisations. TLE
n*logn went through though

inkretbear: 2018-08-23 23:15:18

Was getting WA on #17 with prefix hash

Made my for loop that compared the current solution with a new candidate run twice instead of once

Got AC

hamjosh1: 2016-09-30 13:29:49

learned a lot :D

vsp4: 2016-09-11 19:19:06

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

minhthai: 2016-04-03 05:42:51

"Some accepted solution got TLE."
Please, give some care to Java nlogn solution :((

lakshay_v06: 2016-02-05 15:33:28

Same as http://www.spoj.com/problems/BEADS/ . O(nlogn) passed. :)

Dhawal Harkawat: 2016-01-22 05:30:20

silly mistake costed two WAs at #10. finally AC.

Sumit Vohra: 2016-01-21 23:37:21

solved using suffix automaton in O(n)

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

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


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