题目链接：
题目大意：
给出一个环，每颗珠子有一个甜度，选择第一个珠子和吃的方向，问得到的吃珠子的字符串的字典序最大的，如果有多个，选取位置最靠前的，如果还是多个，选择顺时针吃的。
题目分析：
-首先构造一个字符串，首先正着按环吃，那么就是字符串正着写两遍，连接在一起;中间用没有出现过的字符连接，然后逆时针吃的，也就是反着写两遍连在一起。
- 然后我们找到后缀排序前面与排序第一个的公共前缀大于等于n的所有的情况，然后寻找他们当中符合题意的字符串的即可。起始位置可以通过suffix数组得到。
AC代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 200007
int wwa[maxn],wwb[maxn],wwv[maxn],wws[maxn];
int cmp(int *r,int a,int b,int l){
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sufix,int n,int m){
int i,j,p,*x=wwa,*y=wwb,*t;
for(i=0;i<m;i++)wws[i]=0;
for(i=0;i<n;i++)wws[x[i]=r[i]]++;
for(i=1;i<m;i++)wws[i]+=wws[i-1];
for(i=n-1;i>=0;i--)sufix[--wws[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p){
for(p=0,i=n-j;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)
if(sufix[i]>=j)
y[p++]=sufix[i]-j;
for(i=0;i<n;i++)wwv[i]=x[y[i]];
for(i=0;i<m;i++)wws[i]=0;
for(i=0;i<n;i++)wws[wwv[i]]++;
for(i=1;i<m;i++)wws[i]+=wws[i-1];
for(i=n-1;i>=0;i--)
sufix[--wws[wwv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sufix[0]]=0,i=1;i<n;i++)
x[sufix[i]]=cmp(y,sufix[i-1],sufix[i],j)?p-1:p++;
}
return;
}
int r[maxn];
int rank1[maxn],height[maxn],sufix[maxn];
void calheight(int *r,int *sufix,int n){
int i,j,k=0;
for(i=0;i<=n;i++) rank1[sufix[i]]=i;
for(i=0;i<n;height[rank1[i++]]=k)
for(k?k--:0,j=sufix[rank1[i]-1];r[i+k]==r[j+k];k++);
return;
}
struct Node{
int p,c;
};
int comp(Node a,Node b){
if(a.p == b.p) return a.c < b.c;
return a.p < b.p;
}
Node ans[maxn];
char word[maxn];
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%s",word);
for(int i = 0;i < n; i++){
r[i]=r[i+n] = word[i];
}
int len =n*4+1;
r[n*2] = '#';
for(int i = 0;i < n; i++){
r[i+n*2+1] = r[i+n*3+1] = word[n-i-1];
}
r[len] = 0;
da(r,sufix,len+1,328);
calheight(r,sufix,len);
int cnt = 0;
ans[cnt++].p = sufix[len];
for(int i = len-1;i > 1; i--){
if(height[i+1] < n) break;
if(sufix[i]>=n&&sufix[i]<=n*2) continue;
if(sufix[i]>=n*3+1)continue;
ans[cnt++].p = sufix[i];
}
for(int i = 0;i < cnt; i++){
if(ans[i].p > 2*n){
ans[i].c =1;
ans[i].p = n-(ans[i].p-2*n-1);
}
else {
ans[i].p++;
ans[i].c = 0;
}
}
sort(ans,ans+cnt,comp);
printf("%d %d\n",ans[0].p,ans[0].c);
}
return 0;
}