【bzoj1717】[Usaco2006 Dec]Milk Patterns 产奶的模式

2015.06.15 09:58 Mon | 27次阅读 | 旧日oi | 固定链接 | 源码

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。

题解

SB题不多说了……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#define N 20005 
using namespace std;
int n,m,a[N],p=1,q,ans;
int sa[2][N],rk[2][N],v[1000005],h[N];
multiset<int> s;
void mul(int k,int *sa,int *rk,int *SA,int *RK)
{
    for(int i=1;i<=n;i++) v[rk[sa[i]]]=i;
    for(int i=n;i;i--)
        if(sa[i]>k)
            SA[v[rk[sa[i]-k]]--]=sa[i]-k;
    for(int i=n-k+1;i<=n;i++) SA[v[rk[i]]--]=i;
    for(int i=1;i<=n;i++)
    RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);
}
void get_sa(int lim)
{
    for(int i=1;i<=n;i++) v[a[i]]++;
    for(int i=1;i<=lim;i++) v[i]+=v[i-1];
    for(int i=1;i<=n;i++) sa[p][v[a[i]]--]=i;
    for(int i=1;i<=n;i++) 
        rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
    for(int k=1;k<n;k<<=1,swap(p,q)) mul(k,sa[p],rk[p],sa[q],rk[q]);
    for(int j,k=0,i=1;i<=n;i++)
    {
        j=sa[p][rk[p][i]-1];
        while(a[i+k]==a[j+k]) k++;
        h[rk[p][i]]=k;if(k) k--;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]++;
    get_sa(1000001);
    for(int i=1;i<m;i++) s.insert(h[i]);
    for(int i=m;i<=n;i++)
    {
        s.erase(s.find(h[i-m+1]));s.insert(h[i]);
        ans=max(ans,*s.begin());
    }
    cout<<ans<<endl;
}```