bzoj1717 [Usaco2006 Dec]Milk Patterns 産奶的模式 字尾數組 論文題

這題是羅大神的論文題= =求重複k次的最長子串。

求出height以後二分判斷或者單調隊列都是可以的，我選擇二分w。

實力诠釋一波眼瞎，判斷一個n打成n-1調了半天。。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=+;
int sa[N],rank[N],height[N],nsa[N],nrank[N],sum[N];
int s[N];
int n,k;
inline void sort(int j)
{
    memset(sum,,sizeof(sum));
    fo(i,,n)sum[rank[i+j]]++;
    fo(i,,n)sum[i]+=sum[i-];
    fd(i,n,)nsa[sum[rank[i+j]]--]=i;
    memset(sum,,sizeof(sum));
    fo(i,,n)sum[rank[i]]++;
    fo(i,,n)sum[i]+=sum[i-];
    fd(i,n,)sa[sum[rank[nsa[i]]]--]=nsa[i];
}
inline void gsa()
{
    memset(sum,,sizeof(sum));
    fo(i,,n)rank[i]=s[i];
    fo(i,,n)sum[rank[i]]++;
    fo(i,,N)sum[i]+=sum[i-];
    fd(i,n,)
    sa[sum[rank[i]]--]=i;
    int p=;
    fo(i,,n)
    nrank[sa[i]]=rank[sa[i]]==rank[sa[i-]]?p:++p;
    for(int j=;j<=n;j*=)
    {
        sort(j);
        p=;
        fo(i,,n)
        {
            if (rank[sa[i]]!=rank[sa[i-]]||rank[sa[i]+j]!=rank[sa[i-]+j])p++;
            nrank[sa[i]]=p;
        }
        fo(i,,n)rank[i]=nrank[i];
    }
}

inline void getheight()
{
    int k=;
    fo(i,,n)
    {
        if (k)k--;
        int j=sa[rank[i]-];
        while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
        height[rank[i]]=k;
    }
}
inline bool pd(int x)
{
    int sum=;
    fo(i,,n-)
    {
        if (height[i]>=x)
        {
            sum++;
            if (sum==k-)return ;
        }   else sum=;
    }
    return ;
}
int num[N],hash[N],tot;
inline int find(int x)
{
    int l=,r=tot,ans=;
    while (l<=r)
    {
        int mid=(l+r)>>;
        if (hash[mid]<=x)ans=mid,l=mid+;
        else r=mid-;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&k);
    fo(i,,n)scanf("%d",&s[i]),num[i]=s[i];
    sort(num+,num+n+);
    hash[++tot]=num[];
    fo(i,,n)if (num[i]!=num[i-])hash[++tot]=num[i];
    fo(i,,n)s[i]=find(s[i]);
    gsa();
    getheight();
    int l=,r=n,ans=;
    while (l<=r)
    {
        int mid=(l+r)>>;
        if (pd(mid))ans=mid,l=mid+;
        else r=mid-;
    }
    printf("%d\n",ans);
}