记录编号	251869	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Dec07]最佳老农(金组)	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.050 s
提交时间	2016-04-18 19:14:45	内存使用	0.86 MiB

#include<stdio.h>
#define ll unsigned int
ll hash1[30010],hash2[30010],base[30010];
int n,len,l,r,s[30010];
inline int TS(int L,int R){
	int ans;
	for(int l=0,r=R-L+1,mid;l<=r;){
		mid=l+r>>1;
		ll tmp1=(hash1[L]-hash1[L+mid])*base[L-1];
		ll tmp2=(hash2[R]-hash2[R-mid])*base[n-R];
		if(tmp1==tmp2)ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
int ans[30010];
int main(){
	freopen("bclgold.in","r",stdin);
	freopen("bclgold.out","w",stdout);
	scanf("%d",&n),base[0]=1,base[1]=131;
	for(int i=2;i<=n;++i)base[i]=base[i-1]*base[1];
	for(int i=1;i<=n;++i)
		for(s[i]=getchar();s[i]<'A'||s[i]>'Z';s[i]=getchar());
	for(int i=n;i;--i)
		hash1[i]=hash1[i+1]+base[n-i]*s[i];
	for(int i=1;i<=n;++i)
	    hash2[i]=hash2[i-1]+base[i-1]*s[i];
	for(l=1,r=n;l<=r;){
		len=TS(l,r);
		if(s[l+len]>s[r-len])ans[++ans[0]]=s[r--];
		else ans[++ans[0]]=s[l++];
	}
	for(int i=1;i<=ans[0];++i)putchar(ans[i]);
	//while(1);
}