记录编号	476085	评测结果	AAAAAAAAAAA
题目名称	[USACO Dec06]产奶的模式	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2017-11-21 14:02:56	内存使用	18.09 MiB

//之前就rank[sa[i]]=i
//没有判断sliding window里够不够K-1个
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
#define rank rank2
const int SIZEC=1000010,SIZEN=20010;
void basesort(int a[],int b[],int c[],int n,int m){
    if(m==-1){
        for(int i=0;i<n;i++) m=max(m,c[i]);
    }
    static int sum[SIZEC];
    for(int i=0;i<=m;i++) sum[i]=0;
    for(int i=0;i<n;i++) sum[c[a[i]]]++;
    for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
    for(int i=n-1;i>=0;i--) b[--sum[c[a[i]]]]=a[i];
}
void sort_suf(int S[],int rank[],int sa[],int N){
    static int A[SIZEN],B[SIZEN],x[SIZEN],y[SIZEN];
    for(int i=0;i<N;i++) x[i]=S[i],A[i]=i;
    basesort(A,sa,x,N,-1);
    rank[sa[0]]=1;
    for(int i=1;i<N;i++){
        if(x[sa[i]]==x[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
        else rank[sa[i]]=rank[sa[i-1]]+1;
    }
    for(int k=1;k<=N;k<<=1){
        for(int i=0;i<N;i++){
            x[i]=rank[i];
            y[i]=i+k<N?rank[i+k]:0;
            A[i]=i;
        }
        basesort(A,B,y,N,N);
        basesort(B,sa,x,N,N);
        rank[sa[0]]=1;
        for(int i=1;i<N;i++){
            if(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
            else rank[sa[i]]=rank[sa[i-1]]+1;
        }
    }
    for(int i=0;i<N;i++) rank[sa[i]]=i;
}
void calc_height(int S[],int rank[],int sa[],int height[],int N){
    int h=0;
    for(int i=0;i<N;i++){
        if(rank[i]==0) h=0;
        else{
            int k=sa[rank[i]-1];
            if(--h<0) h=0;
            while(S[i+h]==S[k+h]) h++;
        }
        height[rank[i]]=h;
    }
}
int N,K;
int S[SIZEN];
int rank[SIZEN],sa[SIZEN];
int height[SIZEN];
void work(void){
    if(K==1){
        printf("%d\n",N);
        return;
    }
    sort_suf(S,rank,sa,N);
    calc_height(S,rank,sa,height,N);
    //for(int i=0;i<N;i++){for(int j=sa[i];j<N;j++){cout<<S[j]<<" ";}cout<<endl;}
    //for(int i=0;i<N;i++) cout<<height[i]<<" ";cout<<endl;
    multiset<int> st;
    int ans=0;
    for(int i=0;i<N;i++){
        st.insert(height[i]);
        if(i>=K-1){
            st.erase(height[i-K+1]);
        }
        if(st.size()==K-1) ans=max(ans,*st.begin());
    }
    printf("%d\n",ans);
}
void read(void){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%d",&S[i]);
}
int main(){
    //freopen("input.in","r",stdin);
    freopen("patterns.in","r",stdin);
    freopen("patterns.out","w",stdout);
    read();
    work();
    return 0;
}