题目大意: 给出 n 个数的序列和 m, 求数列中出现至少 m 次的最大长度.
本来可以用 trie 树和 ac 自动机 / trie 图搞一搞, 但是数据范围太大.
后缀数组 + RMQ:
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- #define N 20050
- int n,m,a[N];
- int rank[N],tr[N],sa[N],hs[1000005],h[N];
- struct node
- {
- int x,id;
- }nd[N];
- bool vmp(node a,node b)
- {
- return a.x<b.x;
- }
- bool cmp(int x,int y,int k)
- {
- if(x+k>n||y+k>n)return 0;
- return rank[x]==rank[y]&&rank[x+k]==rank[y+k];
- }
- void get_sa()
- {
- int i,cnt=0;
- for(i=1;i<=n;i++)hs[a[i]]++;
- for(i=1;i<=n;i++)if(hs[i])tr[i]=++cnt;
- for(i=1;i<=n;i++)hs[i]+=hs[i-1];
- for(i=n;i>=1;i--)rank[i]=tr[a[i]],sa[hs[a[i]]--]=i;
- for(int k=1;cnt!=n;k<<=1)
- {
- for(i=1;i<=n;i++)hs[i]=0;
- for(i=1;i<=n;i++)hs[rank[i]]++;
- for(i=1;i<=n;i++)hs[i]+=hs[i-1];
- for(i=n;i>=1;i--)if(sa[i]>k)tr[sa[i]-k]=hs[rank[sa[i]-k]]--;
- for(i=1;i<=k;i++)tr[n-i+1]=hs[rank[n-i+1]]--;
- for(i=1;i<=n;i++)sa[tr[i]]=i;
- for(i=1,cnt=0;i<=n;i++)tr[sa[i]]=cmp(sa[i],sa[i-1],k)?cnt:++cnt;
- for(i=1;i<=n;i++)rank[i]=tr[i];
- }
- }
- int f[N][18];
- void get_h()
- {
- for(int i=1;i<=n;i++)
- {
- if(rank[i]==1)continue;
- for(int j=max(1,h[rank[i-1]]-1);;j++)
- {
- if(a[i+j-1]==a[sa[rank[i]-1]+j-1])h[rank[i]]=j;
- else break;
- }
- f[rank[i]][0]=h[rank[i]];
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- scanf("%d",&nd[i].x),nd[i].id=i;
- sort(nd+1,nd+1+n,vmp);
- int las = -1,cnt = 0;
- for(int i=1;i<=n;i++)
- {
- if(nd[i].x!=las)
- {
- las = nd[i].x;
- cnt++;
- }
- a[nd[i].id]=cnt;
- }
- m--;
- get_sa();
- get_h();
- int lg = -1,u=m;
- while(u)
- {
- lg++;
- u>>=1;
- }
- for(int i=1;i<=lg;i++)
- {
- for(int j=1;j<=n;j++)
- {
- f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
- }
- }
- int ans = -0x7fffffff;
- for(int i=1;i+m-1<=n;i++)
- {
- ans=max(ans,min(f[i][lg],f[i+m-(1<<lg)][lg]));
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2781397.html