Favorite Donut
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1702 Accepted Submission(s): 430
Once Lulu eats a part of the donut, she must continue to eat its uneaten adjacent part until all parts are eaten. Therefore, she has to eat either clockwise or counter-clockwise after her first bite, and there are 2n ways to eat the ring donut of n parts. For example, Lulu has 6 ways to eat a ring donut abc: abc,bca,cab,acb,bac,cba. Lulu likes eating the sweetest part first, so she actually prefer the way of the greatest lexicographic order. If there are two or more lexicographic maxima, then she will prefer the way whose starting part has the minimum index in clockwise order. If two ways start at the same part, then she will prefer eating the donut in clockwise order. Please compute the way to eat the donut she likes most.
For each test case, the first line contains one integer n,n≤20000, which represents how many parts the ring donut has. The next line contains a string consisted of n lowercase alphabets representing the ring donut.
aaab
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+500;
char str[maxn],sp[maxn],revs[maxn],rvsp[maxn];
char tx[3*maxn];
int f[maxn];
int get_max(char *s){ //最大（最小）表示法得到的是正序遍历最大（最小）字典序开始位置。
int i=0,j=1,k=0;
int len=strlen(s);
while(i<len&&j<len){
if(k==len){
break;
}
if(s[(i+k)%len]<s[(j+k)%len]){
i=i+k+1>j? i+k+1:j+1;
k=0;
}else if(s[(i+k)%len]>s[(j+k)%len]){
j=j+k+1>i? j+k+1:i+1;
k=0;
}else{
k++;
}
}
return min(i,j);
}
void get_s_p(char *sr,char *s,int st,int len){ //提取字符串
for(int i=st,k=0;k<len;i++,k++){
sr[i-st]=s[i%len];
}
sr[len]='\0';
}
void rev(char *s,int len){ //反转
for(int i=len-1;i>=0;i--){
revs[len-1-i]=s[i];
} revs[len]='\0';
} void getfail(char *P,int *F){
int m=strlen(P);
F[0]=F[1]=0; int j;
for(int i=1;i<m;i++){
j=F[i];
while(j&&P[i]!=P[j]) j=F[j];
F[i+1]=P[i]==P[j]?j+1:0;
}
}
int kmp(char *T,char *P){
int n=strlen(T),m=strlen(P);
int j=0;
int ret=0;
for(int i=0;i<n-1;i++){
while(j&&P[j]!=T[i]) j=f[j];
if(P[j]==T[i]) j++;
if(j==m){
ret=max(ret,i-m+1); //对于反转后的串，需得到最大位置
j=f[j];
}
}
return ret;
}
int main(){
int t , n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%s",str);
rev(str,n); int ckw=get_max(str);
get_s_p(sp,str,ckw,n); int ctckw=get_max(revs);
get_s_p(rvsp,revs,ctckw,n); strcpy(tx,revs);
strcat(tx,revs); getfail(rvsp,f);
int ans=kmp(tx,rvsp); //在反转后的串中的位置
ans=n-1-ans; //转化为原串中的位置
int d=strcmp(sp,rvsp);
if(d>0){
printf("%d 0\n",ckw+1);
}else if(d<0){
printf("%d 1\n",ans+1);
}else{
if(ckw<=ans){
printf("%d 0\n",ckw+1);
}else{
printf("%d 1\n",ans+1);
}
}
}
return 0;
}