记录编号	214538	评测结果	AAAAAAAAAA
题目名称	2123.[HZOI 2015] Glass Beads	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2015-12-16 15:34:30	内存使用	2.00 MiB

#include<cstdio>
#include<iostream>
#include<cstring>

#define maxn 2001000

using namespace std;

int n;
char s[maxn];

int MinRepresent()
{
	int n=strlen(s+1);
	for(int i=n+1;i<=n+n;i++){
		s[i]=s[i-n];
	}
	int i=1,j=2;
	while(i<=n&&j<=n){
		int k=0;
		while(s[i+k]==s[j+k]&&k<n) k++;
		if(k==n) break;
		if(s[i+k]>s[j+k]){
			i=max(i+k+1,j+1);
		}else{
			j=max(j+k+1,i+1);
		}
	}
	for(int q=min(i,j),k=0;k<n;k++){
		printf("%c",s[q+k]);
	}
	printf("\n");
}

int main()
{
	freopen("MinRepresentations.in","r",stdin);
	freopen("MinRepresentations.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s+1);
	MinRepresent();
}