Rotations

input/code.cpp: In function 'void SA(char*, int)':
input/code.cpp:19:35: warning: array subscript has type 'char' [-Wchar-subscripts]
     for (int i=0; i<n; ++i) c[s[i]]++;
                                   ^
input/code.cpp:21:43: warning: array subscript has type 'char' [-Wchar-subscripts]
     for (int i=n-1; i>=0; --i) ar[--c[s[i]]] = i;
                                           ^
input/code.cpp: In function 'int main()':
input/code.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", input);
     ~~~~~^~~~~~~~~~~~~
input/code.cpp: In function 'void SA(char*, int)':
input/code.cpp:20:37: warning: iteration 2000009 invokes undefined behavior [-Waggressive-loop-optimizations]
     for (int i=1; i<=MAXN; ++i) c[i]+=c[i-1];
                                 ~~~~^~~~~~~~
input/code.cpp:20:20: note: within this loop
     for (int i=1; i<=MAXN; ++i) c[i]+=c[i-1];
                   ~...

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

using namespace std;

const int MAXN = 2000010;

int c[MAXN], *ar, *na, *ra, *nr, a[2][MAXN], r[2][MAXN], hh[MAXN], h[MAXN];
void SA(char *s, int n) { // c[max(MAXN,MAXM)]
// s[0..n); update *ar,*ra,hh[],h[]; O(n ln n)
// ar[i]=k : s[k..n) is i th smallest suffix
// ra[i]=k : s[i..n) is k th smallest suffix
// hh[i]: length of longest common prefix of s[i..n) and the one just smaller than it
// h[i]: length of longest common prefix of i th and (i-1) th smallest suffixes
// 如果處理多個序列, 每個序列後加一個不同並沒出現過的字元, 合併為一個序列處理
    memset(c, 0, sizeof(c));
    ar = a[0]; na = a[1]; ra = r[0]; nr = r[1];
    for (int i=0; i<n; ++i) c[s[i]]++;
    for (int i=1; i<=MAXN; ++i) c[i]+=c[i-1];
    for (int i=n-1; i>=0; --i) ar[--c[s[i]]] = i;
    ra[ar[0]] = 0;
    for (int i=1; i<n; ++i) ra[ar[i]] = ra[ar[i-1]] + (s[ar[i]]!=s[ar[i-1]]);
    for (int k=1; k<n && ra[ar[n-1]]<n-1; k<<=1) {
        for (int i=0; i<n; ++i) c[ra[ar[i]]] = i+1;
        for (int i=n-1; i>=0; --i) if (ar[i]-k >= 0) na[--c[ra[ar[i]-k]]] = ar[i]-k;
        for (int i=n-k; i<n; ++i) na[--c[ra[i]]] = i;
        nr[na[0]] = 0;
        for (int i=1; i<n; ++i) nr[na[i]] = nr[na[i-1]] + ( ra[na[i]]!=ra[na[i-1]] || ( na[i]+k<n && na[i-1]+k<n && ra[na[i]+k]!=ra[na[i-1]+k] ) );
        swap(ar, na); swap(ra, nr);
    }
    for (int i=0; i<n; ++i) ra[ar[i]] = i;
    for (int i=0,j,k; i<n; ++i) {
        if (ra[i] == 0) hh[i] = 0;
        else if ( i==0 || hh[i-1]==0 ) {
            for (j=0, k=ar[ra[i]-1]; i+j<n && j+k<n && s[i+j]==s[j+k]; ++j);
            hh[i] = j;
        }
        else {
            for (j=hh[i-1]-1, k=ar[ra[i]-1]; i+j<n && j+k<n && s[i+j]==s[j+k]; ++j);
            hh[i] = j;
        }
    } for (int i=0; i<n; ++i) h[i] = hh[ar[i]];
}

char input[MAXN];
char arr[MAXN];

int main()
{
    scanf("%s", input);
    strcpy(arr, input);
    strcat(arr, input);
    int n = strlen(input);
    SA(arr, 2 * n);
    int idx = -1;
    for (int i = 0; i < 2 * n; i++)
    {
      if (ar[i] < n)
      {
        idx = ar[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