WA+RE 8pts，

hack 数据：

9 C A A B B D B A C

GDB 观察之后发现二分挂了，但是我瞪不出来哪里挂了。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=5e5+5,P=131,mod=1e9+7;
char s[N];
ll hf[N],hb[N],p[N];
ll queryf(int l,int r) {
	return (hf[r]-hf[l-1]*p[r-l+1]%mod+mod)%mod;
}
ll queryb(int l,int r) {
	return (hb[l]-hb[r+1]*p[r-l+1]%mod+mod)%mod;
}
int calc(int L,int R) {
	int l=1,r=(R-L+1)/2,res=1;
	while(l<=r) {
		int mid=(l+r)/2;
		if(queryf(L,L+mid-1)==queryb(R,R-mid+1)) {res=mid;l=mid+1;}
		else r=mid-1;
	}
	return res;
}
int cnt=0;
void print(int x) {
	cout<<s[x];
	if(++cnt>=80) {cout<<"\n";cnt=0;}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;cin>>n;
	p[0]=1;
	for(int i=1;i<=n;i++) {
		cin>>s[i];
		p[i]=p[i-1]*P%mod;
		hf[i]=(hf[i-1]*P%mod+s[i])%mod;
	}
	for(int i=n;i>=1;i--) hb[i]=(hb[i+1]*P%mod+s[i])%mod;
	int l=1,r=n;
	while(l<=r) {
		if(s[l]<s[r]) print(l++);
		else if(s[r]<s[l]) print(r--);
		else {
			int len=calc(l,r);
			if(s[l+len]<s[r-len]) print(l++);
			else print(r--);
		}
	}
	return 0;
}