Rotations

import fileinput

with fileinput.input(['-']) as input:
    _string = input.readline().rstrip()
    string = _string * 2
    ls = len(string)
    f, k = [-1]*ls, 0
    for j in range(1, ls):
        i = f[j-k-1]
        while i != -1 and string[j] != string[k+i+1]:
            if string[j] < string[k+i+1]:
                k = j - i - 1
            i = f[i]
        if i == -1 and string[j] != string[k+i+1]:
            if string[j] < string[k+i+1]:
                k = j
            f[j-k] = -1
        else:
            f[j-k] = i+1
    print(_string[k:] + _string[0:k])

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: UNKNOWN

Test 9

Verdict: UNKNOWN

Test 10

Verdict: UNKNOWN

Test 11

Verdict: UNKNOWN

Test 12

Verdict: UNKNOWN