标签：就是 顺时针 逆时针 mp算法 turn ios 表示 kmp return
题意
给出一个长度为n的环状由小写字母组成的序列，请找出从何处断开，顺时针还是逆时针，使得字典序最大。如果两个字符串的字典序一样大，那么它会选择下下标最小的那个。如果某个点顺时针逆时针产生的字典序大小相同，那么优先选择顺时针的。
这个题用最大表示法+KMP很容易解决。因为最大表示法找到的是下表最小的那个字典序最大的字符串，所以正向的时候最大表示法找出来的就直接是答案，关键是逆时针的时候。我们将字符串翻转以后用最大表示法找到那个字符串s2，然后用KMP算法在翻转*2后的串中找出最后面的那个s2，这就是逆时针时候的答案。然后比较顺时针和逆时针时候的答案，选取最优的就可以了。
下面是代码。
1 #include 2 #include 3 #include
4 #include 5
6
7 using namespace std;
8 const int maxn=40000+100;
9 char s[maxn],str[maxn];
10 char s1[maxn],s2[maxn];
11 int T,n,ans1,ans2;
12 int get_max(char *S){
13 int len=strlen(S);
14 int i=0,j=1,k=0;
15 while(ilen){
16 int t=S[(i+k)%len]-S[(j+k)%len];
17 if(t==0)k++;
18 else{
19 if(t>0)
20 j+=k+1;
21 else
22 i+=k+1;
23 if(i==j)j++;
24 k=0;
25 }
26 }
27 return min(i,j);
28 }
29 int f[maxn];
30 void get_fail(char *P){
31 int n=strlen(P);
32 f[0]=0,f[1]=0;
33 for(int i=1;i){
34 int j=f[i];
35 while(j&&P[i]!=P[j])j=f[j];
36 f[i+1]=P[i]==P[j]?j+1:0;
37 }
38 }
39 int find(char *T,char *P){
40 int res=0,len=strlen(T),m=strlen(P);
41 get_fail(P);
42 int j=0;
43 for(int i=0;i2*n;i++){
44 while(T[i]!=P[j]&&j)j=f[j];
45 if(T[i]==P[j])j++;
46 if(j==m){
47 if(i-m+1n){
48 res=i-m+1;
49 }
50 }
51 }
52 return res;
53 }
54 int main(){
55 scanf("%d",&T);
56 for(int t=1;t){
57 scanf("%d",&n);
58 scanf("%s",str);
59 ans1=get_max(str);
60 for(int i=0;i){
61 s1[i]=str[(ans1+i)%n];
62 }
63 s1[n]=0;
64 reverse(str,str+n);
65 int j=get_max(str);
66 for(int i=0;i){
67 s2[i]=str[(j+i)%n];
68 }
69 s2[n]=0;
70 for(int i=0;i)
71 str[i+n]=str[i];
72 str[2*n]=0;
73 int ans2=find(str,s2);
74 int ok=0;
75 ans2=n-ans2-1;
76 // printf("%d %d\n",ans1,ans2);
77 // printf("%s\n%s\n",s1,s2);
78
79 for(int i=0;i){
80 if(s1[i]>s2[i]){
81 ok=1;
82 break;
83 }
84 if(s1[i]s2[i]){
85 ok=-1;
86 break;
87 }
88 }
89 ans1++,ans2++;
90 if(ok>0){
91 printf("%d %d\n",ans1,0);
92 }
93 else if(ok0){
94 printf("%d %d\n",ans2,1);
95 }
96 else{
97 if(ans2ans1){
98 printf("%d %d\n",ans2,1);
99 }else if(ans1ans2){
100 printf("%d %d\n",ans1,0);
101 }else{
102 printf("%d %d\n",ans1,0);
103 }
104 }
105 }
106 return 0;
107 }
View Code
这个题显然也可以用后缀数组来搞。跟上面的思路差不多，顺时针的时候可以直接用sa数组找出答案（因为前面的一定长于后面的），关键是逆时针的时候如何找出下标最大的最大字典序的字符串。我们可以利用一下height数组。当height[i]==len的时候，就是我们要的答案。
1 #include 2 #include 3 #include
4 #include 5
6 using namespace std;
7 const int maxn=60000+10;
8 int T,n;
9 char s[maxn];
10 char s1[maxn],s2[maxn];
11 int sa[maxn],c[maxn],x[maxn],y[maxn],height[maxn],rak[maxn];
12 void build_sa(int m){
13 memset(y,-1,sizeof(y));
14 for(int i=0;i0;
15 for(int i=0;i;
16 for(int i=1;i1];
17 for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
18
19 for(int k=1;k1){
20 int p=0;
21 for(int i=n-k;ii;
22 for(int i=0;iif(sa[i]>=k)y[p++]=sa[i]-k;
23
24 for(int i=0;i0;
25 for(int i=0;i;
26 for(int i=1;i1];
27 for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
28 swap(x,y);
29 p=1,x[sa[0]]=0;
30 for(int i=1;i)
31 x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
32 if(p>=n)break;
33 m=p;
34 }
35 }
36
37 void getHeight(){
38 int k=0;
39 for(int i=0;ii;
40 for(int i=0;i){
41 if(k)k--;
42 int j=sa[rak[i]-1];
43 while(s[i+k]==s[j+k])k++;
44 height[rak[i]]=k;
45 }
46 }
47 int R[maxn],num;
48 char str[maxn];
49 int ans1,ans2,len;
50 int main(){
51 scanf("%d",&T);
52 for(int t=1;t){
53 scanf("%d",&len);
54 scanf("%s",str);
55 for(int i=0;i){
56 s[i]=str[i];
57 s[i+len]=str[i];
58 }
59 n=2*len;
60 s[n]=0;
61 build_sa(123);
62 for(int i=n-1;i>=0;i--){
63 if(sa[i]len){
64 ans1=sa[i];
65 break;
66 }
67 }
68 for(int i=0;i)
69 s1[i]=s[i+ans1];
70 reverse(str,str+len);
71 for(int i=0;i){
72 s[i]=str[i];
73 s[i+len]=str[i];
74 }
75 s[n]=0;
76 build_sa(123);
77 getHeight();
78 // printf("%s\n",s);
79 // for(int i=0;i 80 // printf("%d ",sa[i]);
81 // printf("\n");
82 // for(int i=0;i 83 // printf("%d ",height[i]);
84 // printf("\n");
85 for(int i=n-1;i>=0;i--){
86 if(sa[i]len){
87 ans2=sa[i];
88 if(height[i]len)
89 break;
90 }
91 }
92 for(int i=0;i){
93 s2[i]=s[i+ans2];
94 }
95 s2[len]=0;
96 int ok=0;
97 for(int i=0;i){
98 if(s1[i]>s2[i]){
99 ok=1;
100 break;
101 }
102 if(s1[i]s2[i]){
103 ok=-1;
104 break;
105 }
106 }
107 ans2=len-ans2-1;
108 ans1++,ans2++;
109 //printf("%d %d %d\n",ans1,ans2,ok);
110 if(ok>0){
111 printf("%d 0\n",ans1);
112 }else if(ok0){
113 printf("%d 1\n",ans2);
114 }else{
115 if(ans2ans1){
116 printf("%d 1\n",ans2);
117 }else{
118
View Code
【HDU - 5442】Favorite Donut 【最大表示法+KMP/后缀数组】
标签：就是 顺时针 逆时针 mp算法 turn ios 表示 kmp return
原文地址：https://www.cnblogs.com/LQLlulu/p/9536475.html