hdu5442(2015长春赛区网络赛1006)后缀数组+KMP /最小表示法?

题意:给定一个由小写字母组成的长度为 n 的字符串,首尾相连,可以从任意一个字符开始,顺时针或逆时针取这个串(长度为 n),求一个字典序最大的字符串的开始字符位置和顺时针或逆时针。如果有多个字典序最大的字符串,优先选择开始位置靠前的,如果开始位置相同,优先选择顺时针。

这种字符串的问题,第一反应是后缀数组,为了达到首尾相连的目的,所以先复制了一个两倍长的该字符串,然后再将串倒置,也弄成两倍长度,得到顺逆时针的两倍长的串,并对这两个字符串分别做后缀数组,得到 sa 数组(该串字典序第几小的后缀的开始字符是第几个)由于字符串的后缀长度必然不等,因此所有后缀都有确定的名次。

由于我们需要的是该串的循环n个串,所以对于每个 2*n 的串,它的后缀中我们需要的只有前 n 个,而每个串我们需要的也只有它的前 n 个字符,那么就出现了有可能有多个后缀的前 n 个字符是相同的,但是由于后缀的存在,使这些串的名次就有了差别。因此 sa 数组中我们得到的字典序最大的一个串,它的前 n 个字符只能确定是字典序最大的其中之一,因此我们就需要在 2*n 长度的串中找到第一个符合我们要求的串。所以我从得到的字典序最大的串中取出前 n 个字符,用这个串作为模式串在 2*n 串中 KMP 。

在顺时针的串中匹配到开始位置最靠前的第一个相同的串,而因为逆时针的串是将原串的所有字符导致,所以在逆时针串中开始位置越靠前,则它在原串中的开始位置就越靠后,因此我们需要KMP匹配找出的就是在 2*n 串中开始位置最靠后并且在 n 前的一个相同串。

最后再将得到的两个串比较他们的各个情况,输出最符合要求的一个。

恩,rank竟然变成了关键字,导致我当时CE了一发。

后来在被问到的时候我仔细再想了一下,觉得顺时针貌似并不需要用KMP,因为多个前 n 个字符相同的后缀,由于开始位置靠前的后缀长度会更长,所以字典序就会更大,所以我们取一个字典序最大的后缀,它在前 n 个字符相同的后缀串中开始位置也应该是更靠前的,所以我们用后缀数组得到的字典序最大的串就应该是我们需要的一个串,暂时我还没有想到反例。

但是逆时针却必须要匹配一下,因为字典序最大的,在 2*n 的串中开始位置更靠前,但在原串中开始位置就会越靠后,所以就要匹配得到在 2*n 串中最靠后的一个。例子就是 abcabc ,逆时针取的时候字典序最大的后缀开始位置是原串中的最后一个 c ,因此我们需要找出第三个字符 c 。所以我用了KMP。

但是据说有个做法是最小表示法,然而我并不知道那是什么,所以我还是用后缀数组+KMP过的Orz……

  1 #include <iostream>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <stdio.h>
  5 using namespace std;
  6 const int MAXN=40010;
  7
  8 int sa[MAXN];//SA数组,表示将S的n个后缀从小到大排序后把排好序的
  9 //的后缀的开头位置顺次放入SA中
 10 int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量,不需要赋值
 11 int rk[MAXN],height[MAXN];
 12 void build_sa(int s[],int n,int m)
 13 {
 14     int i,j,p,*x=t1,*y=t2;
 15     for(i=0;i<m;i++)c[i]=0;
 16     for(i=0;i<n;i++)c[x[i]=s[i]]++;
 17     for(i=1;i<m;i++)c[i]+=c[i-1];
 18     for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
 19     for(j=1;j<=n;j<<=1)
 20     {
 21         p=0;
 22         for(i=n-j;i<n;i++)y[p++]=i;//后面的j个数第二关键字为空的最小
 23         for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
 24         for(i=0;i<m;i++)c[i]=0;
 25         for(i=0;i<n;i++)c[x[y[i]]]++;
 26         for(i=1;i<m;i++)c[i]+=c[i-1];
 27         for(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(i=1;i<n;i++)
 31             x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
 32         if(p>=n)break;
 33         m=p;//下次基数排序的最大值
 34     }
 35 }
 36
 37 void getHeight(int s[],int n)
 38 {
 39     int i,j,k=0;
 40     for(i=0;i<=n;i++)rk[sa[i]]=i;
 41     for(i=0;i<n;i++)
 42     {
 43         if(k)k--;
 44         j=sa[rk[i]-1];
 45         while(s[i+k]==s[j+k])k++;
 46         height[rk[i]]=k;
 47     }
 48 }
 49
 50 char str[MAXN];
 51 int s0[MAXN];
 52 int s1[MAXN];
 53 int ans0[MAXN];
 54 int ans1[MAXN];
 55 int pp1[MAXN],pp0[MAXN];
 56
 57 int check(int n){
 58     for(int i=0;i<n;++i){
 59         if(ans0[i]<ans1[i])return 1;
 60         else if(ans0[i]>ans1[i])return 0;
 61     }
 62     return -1;
 63 }
 64
 65 int main(){
 66     int T;
 67     scanf("%d",&T);
 68     while(T--){
 69         int n;
 70         scanf("%d",&n);
 71         scanf("%s",str);
 72         for(int i=0;i<=n;i++)s0[i]=str[i]-‘a‘+1;
 73         for(int i=0;i<=n;i++)s0[n+i]=str[i]-‘a‘+1;
 74         s0[2*n]=0;
 75 /*        for(int i=0;i<=2*n;++i)printf("%d ",s0[i]);
 76         printf("\n");*/
 77         build_sa(s0,2*n+1,28);
 78 /*        for(int i=0;i<=2*n;++i)printf("%d ",sa[i]);
 79         printf("\n");*/
 80         int p0,p1;
 81         for(int i=2*n;i>=1;--i){
 82             if(sa[i]<n){p0=sa[i];break;}
 83         }
 84         for(int i=0;i<n;++i){
 85             ans0[i]=s0[p0+i];
 86 //            printf("%d ",ans0[i]);
 87         }
 88 /*        printf("\n");
 89         printf("\n");*/
 90
 91         for(int i=0,j=n-1;i<n;i++,j--)s1[j]=str[i]-‘a‘+1;
 92         for(int i=0,j=n-1;i<n;i++,j--)s1[n+i]=str[j]-‘a‘+1;
 93         s1[2*n]=0;
 94 /*        for(int i=0;i<=2*n;++i)printf("%d ",s1[i]);
 95         printf("\n");*/
 96         build_sa(s1,2*n+1,28);
 97 /*        for(int i=0;i<=2*n;++i)printf("%d ",sa[i]);
 98         printf("\n");*/
 99         for(int i=2*n;i>=1;--i){
100             if(sa[i]<n){p1=sa[i];break;}
101         }
102         for(int i=0;i<n;++i){
103             ans1[i]=s1[p1+i];
104 //            printf("%d ",ans1[i]);
105         }
106
107 /*        printf("\n");
108         printf("\n");
109 */
110         int cc=check(n);
111 //        printf("c%d\n",cc);
112         if(cc==-1){
113             int i,j;
114             pp0[0]=pp0[1]=0;
115             for(i=1;i<n;++i){
116                 j=pp0[i];
117                 while(j&&ans0[i]!=ans0[j])j=pp0[j];
118                 pp0[i+1]=ans0[i]==ans0[j]?j+1:0;
119             }
120             j=0;
121             for(int i=0;i<2*n;++i){
122                 while(j&&s0[i]!=ans0[j])j=pp0[j];
123                 if(s0[i]==ans0[j])j++;
124                 if(j==n){
125                     p0=i-n+1;
126                     break;
127                 }
128             }
129             pp1[0]=pp1[1]=0;
130             for(i=1;i<n;++i){
131                 j=pp1[i];
132                 while(j&&ans1[i]!=ans1[j])j=pp1[j];
133                 pp1[i+1]=ans1[i]==ans1[j]?j+1:0;
134             }
135             j=0;
136             for(int i=0;i<2*n;++i){
137                 while(j&&s1[i]!=ans1[j])j=pp1[j];
138                 if(s1[i]==ans1[j])j++;
139                 if(j==n){
140                     if(i-n+1<n)p1=i-n+1;
141                 }
142             }
143             p1=n-(p1+1);
144         //    printf("p0:%d p1:%d\n",p0,p1);
145             if(p0<p1){
146                 printf("%d 0\n",p0+1);
147             }
148             else if(p0>p1){
149                 printf("%d 1\n",p1+1);
150             }
151             else printf("%d 0\n",p0+1);
152
153         }
154         else if(cc==0){
155             int i,j;
156             pp0[0]=pp0[1]=0;
157             for(i=1;i<n;++i){
158                 j=pp0[i];
159                 while(j&&ans0[i]!=ans0[j])j=pp0[j];
160                 pp0[i+1]=ans0[i]==ans0[j]?j+1:0;
161             }
162             j=0;
163             for(int i=0;i<2*n;++i){
164                 while(j&&s0[i]!=ans0[j])j=pp0[j];
165                 if(s0[i]==ans0[j])j++;
166                 if(j==n){
167                     p0=i-n+1;
168                     break;
169                 }
170             }
171             printf("%d 0\n",p0+1);
172         }
173         else if(cc==1){
174             int i,j;
175             pp1[0]=pp1[1]=0;
176             for(i=1;i<n;++i){
177                 j=pp1[i];
178                 while(j&&ans1[i]!=ans1[j])j=pp1[j];
179                 pp1[i+1]=ans1[i]==ans1[j]?j+1:0;
180             }
181             j=0;
182             for(int i=0;i<2*n;++i){
183                 while(j&&s1[i]!=ans1[j])j=pp1[j];
184                 if(s1[i]==ans1[j])j++;
185                 if(j==n){
186                     if(i-n+1<n)p1=i-n+1;
187             //        p0=i-n+1;
188                 }
189             }
190             p1=n-(p1+1);
191             printf("%d 1\n",p1+1);
192         }
193     }
194     return 0;
195 }

时间: 09-12

hdu5442(2015长春赛区网络赛1006)后缀数组+KMP /最小表示法?的相关文章

hdu5443(2015长春赛区网络赛1007)暴力

题意:给了一个数列,有多个询问,每个询问求某个区间内的最大值 数列长度 1000,询问个数 1000,静态,并不需要RMQ这些,直接暴力 n2 查找每个询问区间取最大值就行了. 1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<math.h> 5 using namespace std; 6 typedef long long ll; 7 const int m

hdu5441(2015长春赛区网络赛1005)类最小生成树、并查集

题意:有一张无向图,一些点之间有有权边,某条路径的值等于路径上所有边的边权的最大值,而某个点对的值为这两点间所有路径的值的最小值,给出多个询问,每个询问有一个值,询问有多少点对满足其值小于等于询问值.点的顺序不同算作不同点对. 这题的做法很类似Kruskal算法.一开始所有的点都为一个并查集,从权值最小的边开始,当加入这条边的时候,这条边连接的两个点(并查集)之间相互到达的路径中,值最小的一个路径一定就是通过这条边的,所以这两点间的值就是这条边的权值.之后每加入一条最小边,如果可以用来合并两个并

2015长春网络赛 1006(后缀数组或者最小表示法)

给一个字符串,这个字符串是首位连起来的,要我们输出从哪个位置开始,顺时针走,还是你时针走,字典序最大 如果字典序最大的字符串有多个,开始的下标越小越好,如果开始的下标又相同,那么顺时针的优先. 原字符串为abab,那么只要在后面加上原字符串,变成abababab#,#是一个很小的字符, 然后进行后缀数组,sa[n-1]就是顺指针字典序最大的下标,n为abababab#的长度 逆时针,只要将字符串倒过来,[email protected],@是一个很大的字符, 然后进行后缀数组, 那么只要遍历ra

2015长春赛区区域赛总结

实在不忍心再回顾一番这段惨痛的回忆. 我现在真心觉得,对于ACM,同样是,如果爱,请深爱.只是肤浅的喜欢实在问心有愧.所以,对于最后队伍拿铁,我爆零的这次经历,我真的觉得不堪回首,想过放弃,但是现在偏偏又想死磕,且当做缘分,继续刷刷刷吧. 首先,说热身赛,总共四道题,我们队三个人各自分别敲一道题.然而我们每个人都要敲题,所以我们就要轮流改代码调试,进度相当之慢,而且也确实被codeblocks编译器和ubuntu系统坑爆了.来之前自己熟悉了系统和编译环境,然而并没有完全适应,所以之前遇到的各种问

Largest Point (2015沈阳赛区网络赛水题)

Problem Description Given the sequence A with n integers t1,t2,?,tn. Given the integral coefficients a and b. The fact that select two elements ti and tj of A and i≠j to maximize the value of at2i+btj, becomes the largest point. Input An positive int

hdu 4277 2012长春赛区网络赛 dfs+hashmap ***

hashmap判重大法好 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0

hdu 4273 2012长春赛区网络赛 三维凸包中心到最近面距离 ***

新模板 1 /* 2 HDU 4273 Rescue 3 给一个三维凸包,求重心到表面的最短距离 4 模板题:三维凸包+多边形重心+点面距离 5 */ 6 7 #include<stdio.h> 8 #include<algorithm> 9 #include<string.h> 10 #include<math.h> 11 #include<stdlib.h> 12 using namespace std; 13 const int MAXN=

hdu 4272 2012长春赛区网络赛 dfs暴力 ***

总是T,以为要剪枝,后来发现加个map就行了 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const

hdu 4274 2012长春赛区网络赛 树形dp ***

设定每个节点的上限和下限,之后向上更新,判断是否出现矛盾 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10