P2852 [USACO06DEC] 牛奶模式

2018-03-29 20:28:29


又双叒叕是一道后缀数组

这次不像之前那么难了然而还是不会

题意:求出现至少k次的最长子串的长度

我们先求出这个序列的het值

然后二分答案

check的时候,把后缀分成若干组

判断有没有一组的后缀数>=k

有则答案可行,否则就从当前这一个后缀重新开始计数

与省选题相比,还是略简单一些

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=2e4+5;
int n,m,a[N];
struct SA
{
    int u,sa[N],rank[N],top[N],tax[N],het[N];
    inline void qsort()
    {
        memset(tax,0,sizeof(tax));
        for (reg int i=1;i<=n;i++) ++tax[rank[i]];
        for (reg int i=1;i<=u;i++) tax[i]+=tax[i-1];
        for (reg int i=n;i>=1;i--)
          sa[tax[rank[top[i]]]--]=top[i];
    }
    inline void getSA()
    {
        for (reg int i=1;i<=n;i++) 
          rank[i]=a[i],top[i]=i;
        u=127; qsort();
        for (reg int w=1,p=0;p<n;u=p,w<<=1)
        {
            p=0;
            for (reg int i=1;i<=w;i++) top[++p]=n-w+i;
            for (reg int i=1;i<=n;i++)
              if (sa[i]>w) top[++p]=sa[i]-w;
            qsort(); swap(rank,top);
            rank[sa[1]]=p=1;
            for (reg int i=2;i<=n;i++)
              if (top[sa[i-1]]==top[sa[i]]&&top[sa[i-1]+w]==top[sa[i]+w])
                rank[sa[i]]=p;
              else rank[sa[i]]=++p;
        }
        int k=0;
        for (reg int i=1;i<=n;i++)
        {
            k=(k?k-1:0);
            while (a[i+k]==a[sa[rank[i]-1]+k]) ++k;
            het[rank[i]]=k;
        }
    }
}R;
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline bool check(int k)
{
    int l=1,r=1;
    for (reg int i=2;i<=n+1;i++)
      if (R.het[i]>=k) ++r;
      else if (r-l+1>=m) return 1;
      else l=r=i;
    return 0;
}
inline int getans()
{
    int l=0,r=n,ans=0;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(mid))
        {
            ans=mid; l=mid+1;
        }
        else r=mid-1;
    }
    return ans;
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;a[i++]=read());
    R.getSA(); 
    printf("%d\n",getans());
    return 0;
}