MINMOVE - Minimum Rotations
English | Vietnamese |
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
|
|
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.
|
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 |