This post is written in Chinese. Please consider using Google Translate

O(N^2)的算法。但由于大数据都比较特殊，所以能很快过了。

由于是一个环，所以要把字符串在复制一遍放到末尾。

我采用C语言对字符串的描述方法，从0开始。

用i,j分别表示以i开头和以j开头的两个长度为L的字符串。i=0，j=1。

比较字符串S[i]和S[j]的大小，如果S[i]>S[j]则i=j，否则j向后移c位，c表示S[i]和S[j]的最长相同前缀的长度或者为1，直到j≥n为止。i的值就是结果。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3044 KB]
   Test 2: TEST OK [0.000 secs, 3044 KB]
   Test 3: TEST OK [0.022 secs, 3044 KB]
   Test 4: TEST OK [0.011 secs, 3040 KB]
   Test 5: TEST OK [0.011 secs, 3044 KB]
   Test 6: TEST OK [0.000 secs, 3044 KB]
   Test 7: TEST OK [0.000 secs, 3044 KB]
   Test 8: TEST OK [0.022 secs, 3044 KB]
   Test 9: TEST OK [0.000 secs, 3044 KB]
   Test 10: TEST OK [0.011 secs, 3040 KB]
   Test 11: TEST OK [0.022 secs, 3044 KB]
   Test 12: TEST OK [0.000 secs, 3044 KB]
   Test 13: TEST OK [0.022 secs, 3040 KB]
   Test 14: TEST OK [0.011 secs, 3040 KB]

All tests OK.

Your program ('hidden') produced all correct answers! This is your submission #10 for this problem. Congratulations! 

/*
ID: cmykrgb1
PROG: hidden
LANG: C++
*/

#include <iostream>
#include <fstream>

using namespace std;


ofstream fo("hidden.out");

char S[200000];
int L;

void init()
{
    freopen("hidden.in","r",stdin);
    char c=10;
    int k=0;
    scanf("%d",&L);
    for (;;)
    {
        while (c==10 || c==13) c=getchar();
        if (c==EOF)    break;
        S[k++]=c;
        c=getchar();
    }
    for (k=0;k<L;k++)
        S[k+L]=S[k];
    S[2*L]=0;
}

void compare()
{
    int i=0,j=1,k,c,bigger;
    while (j<L)
    {
        c=-1;bigger=0;
        for (k=0;k<L;k++)
        {
            if (c!=-1 && bigger!=0) break;
            if (S[i+k]!=S[j+k] && c==-1)
                c=k;
            if (bigger==0)
            {
                if (S[i+k]>S[j+k])
                    bigger=1;
                else if (S[i+k]<S[j+k])
                    bigger=2;
            }
        }
        if (bigger==1)
        {
            i=j++;
        }
        else
            j+=c==0?1:c;
    }
    fo << (i==-1?0:i) << endl;
}

int main()
{
    init();
    compare();
    fo.close();
    return 0;
}