POJ3261：Milk Patterns——题解

http://poj.org/problem?id=3261

论文题+傻逼题。

上一道题（POJ1743）会做即可。

还是二分长度，按照高度数组分组做，统计每个组有多少个后缀即可。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cctype>

#include<cstdio>

#include<vector>

#include<queue>

#include<cmath>

using namespace std;

const int N=2e4+;

int n,m,rank[N],sa[N],height[N],w[N],s[N];

inline bool pan(int *x,int i,int j,int k){

    int ti=i+k<n?x[i+k]:-;

    int tj=j+k<n?x[j+k]:-;

    return x[i]==x[j]&&ti==tj;

}

inline void SA_init(){

    int *x=rank,*y=height,r=;

    for(int i=;i<r;i++)w[i]=;

    for(int i=;i<n;i++)w[s[i]]++;

    for(int i=;i<r;i++)w[i]+=w[i-];

    for(int i=n-;i>=;i--)sa[--w[s[i]]]=i;

    r=;x[sa[]]=;

    for(int i=;i<n;i++)

    x[sa[i]]=s[sa[i]]==s[sa[i-]]?r-:r++;

    for(int k=;r<n;k<<=){

    int yn=;

    for(int i=n-k;i<n;i++)y[yn++]=i;

    for(int i=;i<n;i++)

        if(sa[i]>=k)y[yn++]=sa[i]-k;

    for(int i=;i<r;i++)w[i]=;

    for(int i=;i<n;i++)++w[x[y[i]]];

    for(int i=;i<r;i++)w[i]+=w[i-];

    for(int i=n-;i>=;i--)sa[--w[x[y[i]]]]=y[i];

    swap(x,y);r=;x[sa[]]=;

    for(int i=;i<n;i++)

        x[sa[i]]=pan(y,sa[i],sa[i-],k)?r-:r++;

    }

    for(int i=;i<n;i++)rank[i]=x[i];

}

inline void height_init(){

    int i,j,k=;

    for(i=;i<=n;i++)rank[sa[i]]=i;

    for(i=;i<n;i++){

    if(k)k--;

    else k=;

    j=sa[rank[i]-];

    while(s[i+k]==s[j+k])k++;

    height[rank[i]]=k;

    }

}

bool check(int k){

    int cnt=;

    for(int i=;i<=n;i++){

    if(height[i]>=k){

        cnt++;

    }else cnt=;

    if(cnt>=m)return ;

    }

    return ;

}

int erfen(int l,int r){

    while(l<r){

    int mid=(l+r+)>>;

    if(check(mid))l=mid;

    else r=mid-;

    }

    return l;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++)scanf("%d",&s[i]);

    s[n++]=;

    SA_init();

    n--;

    height_init();

    printf("%d\n",erfen(,n));

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++