3647 - Shift 3647 - Shift 3647 - Shift

Statistics Sub: 258 | AC: 53 | AC%: 20,54 | Score: 2,56
Created by José Luis Castrillón Garrido
Added by jlcastrillon (2016-05-24)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Bono is composing the best song of his life and for this reason he bought a new guitar. A song comes out of the guitar as a string of lowercase characters. Bono loves to play with the songs he writes. This time he is interested in the Shifts of the song.

Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k-1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.
Bono is composing the best song of his life and for this reason he bought a new guitar. A song comes out of the guitar as a string of lowercase characters. Bono loves to play with the songs he writes. This time he is interested in the Shifts of the song.

Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k-1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.
Bono is composing the best song of his life and for this reason he bought a new guitar. A song comes out of the guitar as a string of lowercase characters. Bono loves to play with the songs he writes. This time he is interested in the Shifts of the song.

Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k-1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.

Input specification

The first and only line of input contains the new song T (1 <= length(T) <= 100000). ;jsessionid=B6A63B8FA9CB2D8D9E756C4193E939DA
The first and only line of input contains the new song T (1 <= length(T) <= 100000). ;jsessionid=B6A63B8FA9CB2D8D9E756C4193E939DA
The first and only line of input contains the new song T (1 <= length(T) <= 100000). ;jsessionid=B6A63B8FA9CB2D8D9E756C4193E939DA

Output specification

Output N lines indicating the positions of the ordered Shifts.
Output N lines indicating the positions of the ordered Shifts.
The first and only line of input contains the new song T (1 <= length(T) <= 100000). ;jsessionid=B6A63B8FA9CB2D8D9E756C4193E939DA

Sample input

aba

Sample output

3
1
2

Hint(s)

The ordered shifts for aba are:
3 aab
1 aba
2 baa
The ordered shifts for aba are:
3 aab
1 aba
2 baa
The ordered shifts for aba are:
3 aab
1 aba
2 baa

Recommendation

We have carefully selected several similar problems: 3675 | 3380 | 1721 | 3166 | 1005 | 3091