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;
}

上次修改时间 2017-02-03