欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

后缀数组+二分--luoguP2852 [USACO06DEC]牛奶模式Milk Patterns

程序员文章站 2022-04-17 14:36:31
...

传送门

二分答案,然后后缀数组里再用二分判断,同luoguP3649

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 20005
#define maxm 1000005
using namespace std;

inline int rd(){
	int x=0,f=1;char c=' ';
	while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();
	while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();
	return x*f;
}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}

int n,K,m,s[maxn],sa[maxn],rk[maxn],tp[maxn],tax[maxm],h[maxn],st[maxn][20];

inline void rsort(){
	for(int i=1;i<=m;i++) tax[i]=0;
	for(int i=1;i<=n;i++) tax[rk[i]]++;
	for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
	for(int i=n;i;i--) sa[tax[rk[tp[i]]]--]=tp[i];
}

inline void ssort(){
	for(int i=1;i<=n;i++) rk[i]=s[i],tp[i]=i;
	rsort();
	for(int w=1,p=0;w<=n && p<n;w<<=1,m=p){//m=p!
		p=0;
		for(int i=n-w+1;i<=n;i++) tp[++p]=i;
		for(int i=1;i<=n;i++)
			if(sa[i]>w) tp[++p]=sa[i]-w;
		rsort(); swap(rk,tp);
		rk[sa[1]]=p=1;
		for(int i=2;i<=n;i++)
			if(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])
				rk[sa[i]]=p;
			else rk[sa[i]]=++p;
	}
}

inline void geth(){
	int j,k=0;
	for(int i=1;i<=n;i++){
		if(k) --k;
		j=sa[rk[i]-1];
		while(s[i+k]==s[j+k]) ++k;
		h[rk[i]]=k;
	}
}

inline void prework(){
	for(int i=1;i<=n;i++) st[i][0]=h[i];
	for(int j=1;(1<<j)<n;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

inline int query(int l,int r){
	if(l>r) swap(l,r); ++l;
	int t=log2(r-l+1); return min(st[l][t],st[r-(1<<t)+1][t]);
}

inline int findl(int pos,int len){
	int l=1,r=pos-1,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(query(mid,pos)>=len) r=mid-1;
		else l=mid+1;
	} return l;
}

inline int findr(int pos,int len){
	int l=pos+1,r=n,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(query(mid,pos)>=len) l=mid+1;
		else r=mid-1;
	} return r;
}

inline bool check(int len){
	int cnt=0,l,r;
	for(int i=1;i<=n;i++){
		if(h[i]<len) l=i;
		else l=findl(i,len);
		if(h[i+1]<len) r=i;
		else r=findr(i,len);
		cnt=max(cnt,r-l+1);
	} return cnt>=K;
}

int main(){
	n=rd(); K=rd();
	for(int i=1;i<=n;i++) s[i]=rd(),m=max(m,s[i]);
	ssort(); geth(); prework();
	int l=0,r=n,mid,ans=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}
相关标签: 后缀数组