题意:给一个字符串连成环,然后有两种选择的方式,正序和逆序,要求最大字典序,并且输出选择的方向。0为正向 1为反向。如果有相同的输出最小坐标,如果还有相同的输出正向。

把给定的字符串增加一倍,然后再这个字符串中求长度为n的最大字典序。
这个用最大表示法可以求得最小的起始坐标。
然后再把这个字符串反序,再用最大表示法求反序串的最小起始坐标,但是。这个起始坐标在原串中是最大的起始坐标,因此用kmp可以求反序串的最大起始坐标,转换一下就是原串的最小起始坐标了。
代码:

//author: CHC
//First Edit Time: 2015-09-14 09:14
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
//using namespace std;
typedef long long LL;
const int MAXN=40000+1000;
const int INF = std::numeric_limits<int>::max();
const LL LL_INF= std::numeric_limits<LL>::max();
int next[MAXN];
char str1[MAXN];
void getnext(char *str,int len){
int i=1,j=0;
next[0]=next[1]=0;
while(i++<len){
while(j&&str[j]!=str[i-1])j=next[j];
if(str[j]==str[i-1])++j;
next[i]=j;
}
}
int kmp(char *str1,char *str2){
int n=strlen(str1),m=strlen(str2),i=0,j=0;
getnext(str2,m);
int pre=-1;
while(i<n){
while(j&&str1[i]!=str2[j])j=next[j];
while(j<m&&str1[i]==str2[j])++i,++j;
if(j==m){
//printf("i:%d j:%d\n",i,j);
if(i-j<m) pre=i-j;
//printf("x:%d\n",i-j);
j=next[j];
//return i-j+1;
}
else if(j==0)++i;
//else i+=(j==0);
}
return pre;
}
int getMax(char *str){
int len=strlen(str)>>1;
int i=0,j=1,k=0;
while(i<len&&j<len){
k=0;
while(k<len&&str[i+k]==str[j+k])++k;
if(k>=len)break;
if(str[i+k]>str[j+k])j=j+k+1;
else i=i+k+1;
if(i==j)++j;
}
return std::min(i,j);
}
char str2[MAXN],tmp0[MAXN],tmp1[MAXN];
int main()
{
int t,len;
scanf("%d",&t);
while(t--){
scanf("%d",&len);
scanf("%s",str1);
//int len=strlen(str1);
for(int i=0;i<len;i++)str1[i+len]=str1[i];
str1[len*2]=0;
strcpy(str2,str1);
strrev(str2);
//printf("%s\n",str2);
int pos0=getMax(str1);
int pos1=getMax(str2);
sprintf(tmp0,"%.*s",len,str1+pos0);
sprintf(tmp1,"%.*s",len,str2+pos1);
//printf("%s %s\n",str2,tmp1);
//printf("pos1:%d\n",pos1);
pos1=kmp(str2,tmp1);
//printf("pos1:%d\n",pos1);
//printf("%s %s\n",tmp0,tmp1);
pos0=pos0+1;
pos1=len-pos1;
int _t=strcmp(tmp0,tmp1);
//printf("%d\n",_t);
if(_t>0){
printf("%d 0\n",pos0);
}
else if(_t<0){
printf("%d 1\n",pos1);
}
else {
//printf("%d %d\n",pos0,pos1);
if(pos0<=pos1) printf("%d 0\n",pos0);
else printf("%d 1\n",pos1);
}
//printf("%s\n",str1);
//printf("%s\n",str2);
//printf("%.*s\n",len,str1+pos);
}
return 0;
}