记录编号	162592	评测结果	AAAAAAAAAAA
题目名称	[USACO Dec06]产奶的模式	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-05-18 06:38:07	内存使用	1.03 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>

#define N 40010

using namespace std;

void file(){
	freopen("patterns.in","r",stdin);
	freopen("patterns.out","w",stdout);
}

namespace SAM{
	struct node{
		node* ch[27];
		node *fa;
		int len,R,maxv;
	}*last,*root,spT[N],*b[N];
	
	int f[N],tot,cnt[N];
	
	void init(){
		root=&spT[++tot];
		last=root;
	}
	
	void topsort(int n){
		for(int i=1;i<=tot;i++) cnt[spT[i].len]++;
		for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
		for(int i=1;i<=tot;i++) b[cnt[spT[i].len]--]=&spT[i];
	}
	
	void addin(int t){
		node *np=&spT[++tot],*now=last;
		np->len=last->len+1;
		last=np;
		for(;now&&!now->ch[t];now=now->fa) now->ch[t]=np;
		if(!now) np->fa=root;
		else if(now->len+1==now->ch[t]->len)
			np->fa=now->ch[t];
		else{
			node *nq=&spT[++tot],*q=now->ch[t];
			*nq=*q;
			nq->len=now->len+1;
			np->fa=q->fa=nq;
			for(;now&&now->ch[t]==q;now=now->fa)
				now->ch[t]=nq;
		}
	}
	
	void ask(int *S,int n,int K){
		node* p=root;
		for(int i=0;i<n;i++){
			p=p->ch[S[i]];
			p->R++;
		}
		for(int i=tot;i>=1;i--){
			node* tmp=b[i];
			f[tmp->len]=max(f[tmp->len],tmp->R);
			if(tmp->fa) tmp->fa->R+=tmp->R;
		}
		for(int i=n;i>=1;i--) f[i]=max(f[i],f[i+1]);
		int ans=0;
		for(int i=1;i<=n;i++) if(f[i]>=K) ans=i;
		printf("%d\n",ans);
	}
}

int S[N],n,K;

int main(){
	file();
	scanf("%d%d",&n,&K);
	for(int i=0;i<n;i++) scanf("%d",&S[i]);
	SAM::init();
	for(int i=0;i<n;i++) SAM::addin(S[i]);
	SAM::topsort(n);
	SAM::ask(S,n,K);
	fclose(stdin);
	fclose(stdout);
	return 0;
}