洛谷 P2852 【USACO06DEC】Milk Patterns G 题解

xiaoh 2020-6-10

题意

给定一个长度为 $n$ 的序列 $a$ ( $1\leq n\leq 20000,1\leq a_i\leq 1000000$ ),求其中至少出现了 $k$ 次的子串的最大长度( $2\leq k\leq n$ ).

题解

看到熟悉的子串数量就想到了后缀数组.首先按照常规方法将 $sa$ 数组和 $height$ 数组求出.接下来我们在 $height$ 的下标为准考虑问题，显然这对问题本身是没有影响的.如果我们选 $k$ 个子串不妨设其的 $height$ 值为 $h_{b_1},h_{b_2},h_{b_3},\dots,h_{b_k}$ ,其中 $b_1-b_k$ 单调递增.那么显然根据定义,此时能够选取的最大子串的长度为这些子串的 $lcp$ ,即 $\min\{h_b\}$ ,根据贪心可得,必定有一组答案满足 $b_1-b_k$ 为连续的一段下标.所以我们考虑使用单调队列进行处理,即可计算出满足条件的最大的 $lcp$ 的长度.需要注意的一点是序列中的数值较大,因此需要使用离散化以便于基数排序,时间复杂度为 $O(n\log n)$

(当然呢,本题的数据还是想当水的,复杂度相当的宽裕,所以实际上你可以用 $set$ 来进行维护,也可以在时限内进行维护.复杂度与上述一致,只是常数比原来略大)

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int 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^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=20010,LOGN=15;
int n,m,q;
int a[MAXN],b[MAXN];
int c[MAXN],x[MAXN*2],y[MAXN*2],sa[MAXN],rk[MAXN],h[MAXN];
map<int,int> mp;
inline void prework()
{
    sort(b,b+n);
    for(register int i=0;i<n;++i)
    if(!mp[b[i]]) mp[b[i]]=++m;
    for(register int i=0;i<n;++i) a[i]=mp[a[i]];
}
inline void SA()
{
    for(register int i=0;i<n;++i) ++c[x[i]=a[i]];
    for(register int i=1;i<=m;++i) c[i]+=c[i-1];
    for(register int i=n-1;i>=0;--i) sa[--c[x[i]]]=i;
    register int num;
    for(register int k=1;k<n;k<<=1)
    {
        num=0;
        for(register int i=n-k;i<n;++i) y[num++]=i;
        for(register int i=0;i<n;++i)
        if(sa[i]>=k) y[num++]=sa[i]-k;
        for(register int i=0;i<=m;++i) c[i]=0;
        for(register int i=0;i<n;++i) ++c[x[y[i]]];
        for(register int i=1;i<=m;++i) c[i]+=c[i-1];
        for(register int i=n-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i];
        num=0;
        swap(x,y);
        x[sa[0]]=0;
        for(register int i=1;i<n;++i) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])? num:++num;
        if(num==m) return;
        m=num;
    }
}
inline void geth()
{
    register int k=0;
    for(register int i=0;i<n;++i) rk[sa[i]]=i;
    for(register int i=0;i<n;++i)
    {
        if(!rk[i]) continue;
        if(k) --k;
        register int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&a[i+k]==a[j+k]) ++k;
        h[rk[i]]=k;
    }
}
int que[MAXN];
int hd=1,tl=0;
int ans=0;
int main()
{
    read(n),read(q);
    for(register int i=0;i<n;++i) read(a[i]),b[i]=a[i];
    prework();
    SA();//计算后缀数组
    geth();//计算height
    for(register int i=0;i<q-1;++i)//单调队列最开始的一段进行特殊处理
    {
        while(hd<=tl&&h[que[tl]]>=h[i]) --tl;
        que[++tl]=i;
		ans=max(ans,h[que[hd]]);
    }
    ans=max(ans,h[que[hd]]);
    for(register int i=q-1;i<n;++i)//单调队列进行计算,注意下标差是q-1而非q,以及等号的问题
    {
        while(hd<=tl&&i-que[hd]>=q-1) ++hd;
        while(hd<=tl&&h[que[tl]]>=h[i]) --tl;
        que[++tl]=i;
		ans=max(ans,h[que[hd]]);
    }
    write(ans),putchar('\n');
	return 0;
}