记录编号	121379	评测结果	AAAAAAAAAA
题目名称	[USACO Dec06]产奶的模式	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2014-09-19 17:44:54	内存使用	1.11 MiB

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<map>
using namespace std;
const int MAXN=20000+10;
#define CL(x) memset((x),0,sizeof(x))
struct suffix_array{
	int str[MAXN],len;  //the string head is str[1],tail is str[len];
	int sa[MAXN],rank[MAXN],height[MAXN];
	
	void init(){
		CL(str);CL(sa);CL(rank);CL(rank);CL(height);
		len=0;
	}
	suffix_array(){ init(); }
	
	struct element{
		int x[2],id;
	}RE[MAXN],RT[MAXN];
	int C[MAXN];
	
	bool radix_sort(){
		
		for(int p=1;p>=0;p--){
			memset(C,0,sizeof(C));
			for(int i=1;i<=len;i++) C[ RE[i].x[p] ]++;
			for(int i=1;i<MAXN;i++) C[i]+=C[i-1];//////////
			
			for(int i=len;i>=1;i--) RT[ C[RE[i].x[p]]-- ]=RE[i];
			for(int i=1;i<=len;i++) RE[i]=RT[i];
		}
		
		bool have_rep=false;
		
		for(int i=1;i<=len;i++){
			rank[ RE[i].id ]=i;
			if(i>1){
				bool equal= RE[i].x[0]==RE[i-1].x[0] && RE[i].x[1]==RE[i-1].x[1];
				if(equal){
					have_rep=true;
					rank[ RE[i].id ]=rank[ RE[i-1].id ];
				}
			}
		}
		return have_rep;
	}
	
	void cal_sa(){
		for(int i=1;i<=len;i++)
			RE[i].id=i, RE[i].x[0]=str[i], RE[i].x[1]=0;
		radix_sort();
		
		for(int k=1;k<len;k*=2){
			for(int i=1;i<=len;i++)
				RE[i].id=i, RE[i].x[0]=rank[i] ,RE[i].x[1]= i+k<=len ? rank[i+k]:0;
			bool have_rep=radix_sort();
			if(!have_rep) break;
		}
		
		for(int i=1;i<=len;i++)
			sa[ rank[i] ]=i;
	}
	
	void cal_height(){
		int h=0;
		height[1]=0;
		for(int i=1;i<=len;i++){
			if( rank[i]==1 ){
				h=0;
				continue;
			}
			
			int k=sa[ rank[i]-1 ];
			if(--h<0)h=0;
			while(str[i+h]==str[k+h] && i+h<=len && k+h<=len) h++;
			height[ rank[i] ]=h;
		}
	}
}SA;

void test(){
	SA.init();
	char str[]="aabaaaab";
	int k=0;
	for(int i=1;str[k];i++){
		SA.str[i]=str[k++];
		SA.len=i;
	}
	SA.cal_sa();
	SA.cal_height();
	
	for(int i=1;i<=SA.len;i++) printf("%d ",SA.height[i]);
	printf("\n");
}

int nums[MAXN];
int N,K;
void init(){
	scanf("%d %d",&N,&K);
	map<int,int> m;
	int cnt=0;
	for(int i=1;i<=N;i++){
		scanf("%d",&nums[i]);
		if(m.find(nums[i])==m.end())
			m[nums[i]]=cnt++;
	}
	for(int i=1;i<=N;i++)
		nums[i]=m[nums[i]];
		
	SA.init();
	for(int i=1;i<=N;i++){
		SA.str[i]=nums[i];
		SA.len=i;
	}
	SA.cal_sa();
	SA.cal_height();
}

void set_erase(multiset<int> & s,int num){
	multiset<int>::iterator it=s.find(num);
	s.erase(it);
}

void work(){
	multiset<int> s;
	for(int i=2;i<=K-1;i++)
		s.insert( SA.height[i] );
	
	int ans=0;
	for(int i=K;i<=N;i++){
		s.insert( SA.height[i] );
		int tmp_ans=*(s.begin());
		ans=max(ans,tmp_ans);

		
		set_erase(s,SA.height[i-K+2]);
	}
	
	printf("%d\n",ans);
}

int main(){
	//test();
	//freopen("in.txt","r",stdin);
	freopen("patterns.in","r",stdin);
	freopen("patterns.out","w",stdout);
	init();
	work();
	return 0;
}