题意:给一个字符串连成环,然后有两种选择的方式,正序和逆序,要求最大字典序,并且输出选择的方向。0为正向 1为反向。如果有相同的输出最小坐标,如果还有相同的输出正向。
把给定的字符串增加一倍,然后再这个字符串中求长度为n的最大字典序。
这个用最大表示法可以求得最小的起始坐标。
然后再把这个字符串反序,再用最大表示法求反序串的最小起始坐标,但是。这个起始坐标在原串中是最大的起始坐标,因此用kmp可以求反序串的最大起始坐标,转换一下就是原串的最小起始坐标了。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> #include <limits>
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){ if(i-j<m) pre=i-j; j=next[j]; } else if(j==0)++i; } 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); for(int i=0;i<len;i++)str1[i+len]=str1[i]; str1[len*2]=0; strcpy(str2,str1); strrev(str2); int pos0=getMax(str1); int pos1=getMax(str2); sprintf(tmp0,"%.*s",len,str1+pos0); sprintf(tmp1,"%.*s",len,str2+pos1); pos1=kmp(str2,tmp1); pos0=pos0+1; pos1=len-pos1; int _t=strcmp(tmp0,tmp1); if(_t>0){ printf("%d 0\n",pos0); } else if(_t<0){ printf("%d 1\n",pos1); } else { if(pos0<=pos1) printf("%d 0\n",pos0); else printf("%d 1\n",pos1); } } return 0; }
|