BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式 [后缀数组]

1717: [Usaco2006 Dec]Milk Patterns 产奶的模式

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1017 Solved: 561
[Submit][Status][Discuss]

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。

Input

* Line 1: 两个整数 N,K。

* Lines 2..N+1: 每行一个整数表示当天的质量值。

Output

* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度

Sample Input

8 2
1
2
3
2
3
2
3
1

Sample Output

Source

Gold

可重叠的k次最长重复子串

二分最长的程度mid，然后把后缀排序结果sa分组，一组中height>=mid，如果有一组中的个数>=k那么长度mid可行

这是一个常用的技巧：按照排序后后缀的LCP(height)分组

本题数组中元素可以为0。。。。貌似没什么影响

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N=2e4+,M=1e6+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m,k;

int a[N];

int sa[N],c[M],t1[N],t2[N],rnk[N],height[N];

void getHeight(){

    for(int i=;i<=n;i++) rnk[sa[i]]=i;

    int k=;

    for(int i=;i<=n;i++){

        if(k) k--;

        if(rnk[i]==) continue;

        int j=sa[rnk[i]-];

        while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k]) k++;

        height[rnk[i]]=k;

    }

}

inline bool cmp(int *r,int a,int b,int j){

    return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];

}

void getSA(){

    int *r=t1,*y=t2;

    for(int i=;i<=m;i++) c[i]=;

    for(int i=;i<=n;i++) c[r[i]=a[i]]++;

    for(int i=;i<=m;i++) c[i]+=c[i-];

    for(int i=n;i>=;i--) sa[c[a[i]]--]=i;

    for(int j=;j<=n;j<<=){

        int p=;

        for(int i=n-j+;i<=n;i++) y[++p]=i;

        for(int i=;i<=n;i++) if(sa[i]>j) y[++p]=sa[i]-j;

        for(int i=;i<=m;i++) c[i]=;

        for(int i=;i<=n;i++) c[r[y[i]]]++;

        for(int i=;i<=m;i++) c[i]+=c[i-];

        for(int i=n;i>=;i--) sa[c[r[y[i]]]--]=y[i];

        swap(r,y);p=;r[sa[]]=++p;

        for(int i=;i<=n;i++) r[sa[i]]=cmp(y,sa[i],sa[i-],j)?p:++p;

        if(p>=n) break;m=p;

    }

}

bool check(int mid){

    int cnt=;

    for(int i=;i<=n;i++){

        if(height[i]>=mid){

            cnt++;

            if(cnt>=k) return true;

        }else cnt=;

    }

    return false;

}

void solve(){

    int l=,r=n,ans=;

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid)) l=mid+,ans=mid;

        else r=mid-;

    }

    printf("%d",ans);

}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();k=read();

    for(int i=;i<=n;i++) a[i]=read(),m=max(m,a[i]);

    getSA();

    getHeight();

    solve();

}

秒客网