String rotation - MarisaOJ: Marisa Online Judge

A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of

$marisa$ are

$marisa$ ,

$amaris$ ,

$samari$ ,

$isamar$ ,

$risama$ and

$arisam$ . Your task is to determine the lexicographically minimal rotation of a string. ### Input - The first line contains a string

$S$ . ### Output - Print the lexicographically minimal rotation. ### Constraints -

$1 \le |S| \le 10^6$ . ### Example Input:

$marisa$

Output:

$amaris$

Topic

String

Hashing

Rating

1300

Solution (0)

Solution