【BZOJ-1717】Milk Patterns产奶的模式后缀数组

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

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 881 Solved: 480
[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

HINT

Source

Gold

Solution

后缀数组求可重叠的k次最长重复子串

先二分答案，然后对后缀分组

判断是否存在一个组，其后缀个数>=K,如果存在则存在解,否则不存在

时间复杂度O(nlogn)

Code

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define maxn 20002 
int n,K;
int ws[maxn],wv[maxn],wa[maxn],wb[maxn];
int S[maxn],SA[maxn];
inline int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
inline void DA(int *r,int *sa,int n,int m)
{
    int p,*x=wa,*y=wb,*t;
    for (int i=0; i<m; i++) ws[i]=0;
    for (int i=0; i<n; i++) ws[x[i]=r[i]]++;
    for (int i=1; i<m; i++) ws[i]+=ws[i-1];
    for (int i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;
    p=1; for (int j=1; p<n; j*=2,m=p)
        {
            p=0; for (int i=n-j; i<n; i++) y[p++]=i;
            for (int i=0; i<n; i++) if (sa[i]>=j) y[p++]=sa[i]-j;
            for (int i=0; i<n; i++) wv[i]=x[y[i]];
            for (int i=0; i<m; i++) ws[i]=0;
            for (int i=0; i<n; i++) ws[wv[i]]++;
            for (int i=1; i<m; i++) ws[i]+=ws[i-1];
            for (int i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];
            t=x,x=y,y=t;p=1;x[sa[0]]=0;
            for (int i=1; i<n; i++)
                x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
        }
}
int rank[maxn],height[maxn];
inline void calheight(int *r,int *sa,int n)
{
    int k=0;
    for (int i=1; i<=n; i++) rank[sa[i]]=i;
    for (int i=0; i<n; height[rank[i++]]=k)
        {k?k--:0;for (int j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);}
}
inline bool check(int x)
{
    int tmp=0,cnt=0;
    for (int i=1; i<=n; i++)
        {
            if (height[i]<x) 
                {if (cnt>tmp) tmp=cnt;cnt=0;}
            else 
                if (!cnt) cnt=2; else ++cnt;
        }
    if (cnt>tmp) tmp=cnt;
    if (tmp>=K) return 1;
        else return 0;
}
int main()
{
    n=read(),K=read();
    for (int i=0; i<n; i++) S[i]=read();
    S[n]=0;
    DA(S,SA,n+1,20001);
    calheight(S,SA,n);
    int l=1,r=n,mid;
    while (l<r)
        {
            mid=(l+r+1)>>1;
            if (check(mid)) l=mid;
                else r=mid-1;
        }
    printf("%d
",l);
    return 0;
}

在BZOJ上企图冲一波榜,rk1,rk2 0ms打表..并列rk3,实际rk6压了好久愣是上不去了,纸张!