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

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


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