Rotations

input/code.cpp: In function 'int main()':
input/code.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", input);
     ~~~~~^~~~~~~~~~~~~

#include <cstdio>
#include <cstring>
//#include <algorithm>

const int maxn = 2000010;

int A[maxn], B[maxn], C[maxn], D[maxn], *sa = D + 1, *rank, *height;
void sortAndRank(int *a1, int *a2, int n, int &m, int j) {
  int i;  memset(C, 0, sizeof(C));
  for(i = 0; i < n; i ++)    C[a1[i]] ++;
  for(i = 1; i <=m; i ++)    C[i] += C[i-1];
  for(i = n-1; i >= 0; i --)    sa[--C[a1[a2[i]]]] = a2[i];
  a2[sa[0]] = m = 0;
  for(i = 1; i < n; i ++)
a2[sa[i]] = a1[sa[i-1]]==a1[sa[i]] && a1[sa[i-1]+j]==a1[sa[i]+j] ? m : ++ m;
}
void da(char*str, int n, int m) {
  int *a1 = A, *a2 = B, *tmp;  int i, j, p;
  for(i = 0; i < n; i ++) {    a1[i] = i;    a2[i] = str[i];  }
  a1[n] = a2[n] = -1;
  sortAndRank(a2, a1, n, m, 0);
  for(j = 1; m < n-1; j <<= 1) {
    p = 0;
    for(i = n-j; i < n; i ++)  a2[p ++] = i;
    for(i= 0; i < n; i ++)    if(sa[i]>=j)  a2[p ++] = sa[i]-j;
    sortAndRank(a1, a2, n, m, j);
    tmp = a1;  a1 = a2;  a2 = tmp;
  }  rank = a1;  height = a2;
}
void calHeight(char *str, int n) {
  int i, j, k;
  sa[-1] = n;
  for(height[0] = k = i = 0; i < n; i ++) {
    for(k ? k-- : 0, j = sa[rank[i]-1]; str[i+k]==str[j+k]; k++);
    height[rank[i]] = k;
  }
}


char input[maxn];
char arr[maxn];

int main()
{
    scanf("%s", input);
    strcpy(arr, input);
    strcat(arr, input);
    int n = strlen(input);
    da(arr, 2 * n, 1000);
    int idx = -1;
    for (int i = 0; i < 2 * n; i++)
    {
      if (sa[i] < n)
      {
        idx = sa[i];
        break;
      }
    }
    //for (int i = 0; i < 2* n; i++)
    //{
    //  printf("%s\n", arr + ar[i]);
    //}
    arr[idx + n] = 0;
    printf("%s\n", arr + idx);
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED