本文正體字版由OpenCC轉換

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