Rotations

def LSC(S):
  S+=S
  f=[-1]*len(S);
  k=0;
  for j in range(1,len(S)):
    i = f[j-k-1]
    while i!=-1 and S[j]!=S[k+i+1]:
      if S[j] < S[k+i+1]: k=j-i-1
      i = f[i]
    if i==-1 and S[j] != S[k+i+1]:
      if S[j] < S[k+i+1]: k=j
      f[j-k]=-1
    else: f[j-k]=i+1
  return k
s=raw_input()
k = LSC(s)
print (s+s)[k:k+len(s)]

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: UNKNOWN

Test 9

Verdict: UNKNOWN

Test 10

Verdict: UNKNOWN

Test 11

Verdict: UNKNOWN

Test 12

Verdict: UNKNOWN