MINMOVE - Minimum Rotations

no tags 

Cho một xâu S[1..n]. Ta định nghĩa một phép xoay trên S là việc chuyển kí tự đầu tiên của S về cuối xâu. Cụ thể là, sau một phép xoay thì S trở thành T = S[2..n] + S[1].

Ví dụ: S = abcaa, thì sau một phép xoay ta có S = bcaaa.

Tìm số phép xoay ít nhất để biến S thành xâu có thứ tự từ điển nhỏ nhất.

Input

Một dòng duy nhất chứa xâu S. S chỉ chứa các chữ cái in thường trong bảng chữ cái tiếng Anh (‘a’ .. ‘z’), và độ dài của S không quá 100000.

Output

Một dòng duy nhất chứa một số nguyên biểu thị số phép xoay ít nhất.

Example

Input:
mississippi

Output:
10

Bộ test và giới hạn thời gian đã được cập nhật. Một số bài đã bị "chạy quá lâu" :)


hide comments
rising_stark: 2024-06-30 16:25:59

@coolcoder_iith How did you know it timed out at 12?

Finally my O(n*logn) solution got accepted. My previous attempt of O(n*logn*logn) solution gave a TLE

Last edit: 2024-06-30 16:41:18
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)


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