POJ3261 Milk Patterns 后缀数组+二分

这道题据说是后缀数组的水题emmmmm...然而我这个菜鸡什么都不会啊555555...

题意：找出至少出现k次的可重叠的最长子串的长度

之前做POJ1743有一点点基础，通过这道题对各个数组的理解更深入了。画了一个后缀树，好理解多了：（参考博客Orz：https://www.cnblogs.com/jinkun113/p/4743694.html）

据说要先离散化，但是不离散化也能过，我写的没有离散化的。思路就是二分长度，判断出现次数。即利用height值进行分组，再判断有没有哪一组的后缀数量(num初始化为1)>=k。我还是理解不了啊啊啊啊55555...记录下来回头再多看看QAQ...

附上参考博客Orz：https://blog.****.net/libin56842/article/details/46236377

有人总结过（附上总结博客Orz：https://blog.****.net/brandohero/article/details/41938695）：使用后缀数组解题时，遇到“最长”，除了特殊情况外（如可重叠最长重复子串，即height数组最大值），一般需要二分答案，利用height值进行分组。

附上AC代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
typedef pair<int,int>pp;
#define mkp make_pair
#define pb push_back
const int INF=0x3f3f3f3f;
const ll MOD=1e9+(ll)7;

const int MAX=20005;
int n,k;

int t1[MAX],t2[MAX],c[MAX];
bool cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
int sa[MAX];
int ran[MAX];
int height[MAX];
void da(int str[],int n,int m)
{
    n++;
    int i,j,p,*x=t1,*y=t2;
    for(i=0;i<m;i++) c[i]=0;
    for(i=0;i<n;i++) c[x[i]=str[i]]++;
    for(i=1;i<m;i++) c[i]+=c[i-1];
    for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(j=1;j<=n;j<<=1)
    {
        p=0;
        for(i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++)
            if(sa[i]>=j)
                y[p++]=sa[i]-j;
        for(i=0;i<m;i++) c[i]=0;
        for(i=0;i<n;i++) c[x[y[i]]]++;
        for(i=1;i<m;i++) c[i]+=c[i-1];
        for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
        if(p>=n)
            break;
        m=p;
    }
    int k=0;
    n--;
    for(i=0;i<=n;i++)
        ran[sa[i]]=i;
    for(i=0;i<n;i++)
    {
        if(k)
            k--;
        j=sa[ran[i]-1];
        while(str[i+k]==str[j+k])
            k++;
        height[ran[i]]=k;
    }
}

bool check(int x)
{
    int num=1;//要初始化为1(不理解QAQ...)
    for(int i=2;i<=n;i++)
    {
        if(height[i]>=x)
            num++;
        else//重新分组
            num=1;
        if(num>=k)
        {
            //cout<<"x="<<x<<" num="<<num<<endl;
            return true;//x偏小
        }
    }
    //cout<<"x="<<x<<" num="<<num<<endl;
    return false;
}

int r[MAX];
int main()
{
    while(scanf("%d%d",&n,&k)==2)
    {
        int m=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&r[i]);
            m=max(m,r[i]);
        }
        r[n]=0;
        memset(sa,0,sizeof(sa));
        memset(ran,0,sizeof(ran));
        memset(height,0,sizeof(height));
        da(r,n,m+1);
        /*for(int i=1;i<=n;i++)
            cout<<"i="<<i<<" sa="<<sa[i]<<endl;
        for(int i=1;i<=n;i++)
            cout<<"i="<<i<<" sa[i-1]="<<sa[i-1]<<" sa[i]="<<sa[i]<<" height="<<height[i]<<endl;*/

        int l=0,r=n,mid;
        while(l<=r)
        {
            mid=(l+r)/2;
            //cout<<"l="<<l<<" r="<<r<<" mid="<<mid<<endl;
            if(check(mid))
                l=mid+1;
            else
                r=mid-1;
        }
        l--;
        printf("%d\n",l);
    }
	return 0;
}

POJ3261 Milk Patterns 后缀数组+二分

相关推荐