[hihocoder1407]后缀数组二·重复旋律2(后缀数组,二分)

发布于 2018-03-20  68 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[hihocoder1407]后缀数组二·重复旋律2(后缀数组,二分)

Description

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。

旋律可以表示为一段连续的数列,相似的旋律在原数列不可重叠,比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次,2 3 出现了两次,小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少?

Tag

后缀数组,二分

解决思路

这一题的基础上,要求不能出现重叠。考虑到这个答案具有单调性,那么我们二分这个长度是多少,二分判定的时候,判断在连续的一段Height大于等于当前二分长度的后缀中,是否存在两者距离超过当前二分长度的。
需要注意在不连续的时候要更新当前的min和max。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101000;
const int inf=2147483647;

int n;
int Arr[maxN];
int CntA[maxN+20],CntB[maxN+20],SAA[maxN];
int SA[maxN],Rank[maxN],Height[maxN];
int A[maxN],B[maxN];

bool Check(int mid);

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    //后缀数组构造
    for (int i=1;i<=n;i++) cin>>Arr[i];
    for (int i=1;i<=n;i++) CntA[Arr[i]]++;
    for (int i=1;i<=maxN;i++) CntA[i]+=CntA[i-1];
    for (int i=n;i>=1;i--) SA[CntA[Arr[i]]--]=i;
    Rank[SA[1]]=1;
    for (int i=2;i<=n;i++)
    {
        Rank[SA[i]]=Rank[SA[i-1]];
        if (Arr[SA[i]]!=Arr[SA[i-1]]) Rank[SA[i]]++;
    }
    for (int l=1;Rank[SA[n]]<n;l=l<<1)
    {
        for (int i=0;i<=maxN;i++) CntA[i]=CntB[i]=0;
        for (int i=1;i<=n;i++)
        {
            CntA[A[i]=Rank[i]]++;
            CntB[B[i]=((i+l<=n)?(Rank[i+l]):(0))]++;
        }
        for (int i=1;i<=maxN;i++) CntA[i]+=CntA[i-1],CntB[i]+=CntB[i-1];
        for (int i=n;i>=0;i--) SAA[CntB[B[i]]--]=i;
        for (int i=n;i>=0;i--) SA[CntA[A[SAA[i]]]--]=SAA[i];
        Rank[SA[1]]=1;
        for (int i=2;i<=n;i++)
        {
            Rank[SA[i]]=Rank[SA[i-1]];
            if ((A[SA[i]]!=A[SA[i-1]])||(B[SA[i]]!=B[SA[i-1]])) Rank[SA[i]]++;
        }
    }
    for (int i=1,j=0;i<=n;i++)
    {
        if (j) j--;
        while (Arr[i+j]==Arr[SA[Rank[i]-1]+j]) j++;
        Height[Rank[i]]=j;
    }
    //二分判定
    int l=0,r=n;
    int Ans=0;
    do
    {
        int mid=(l+r)>>1;
        if (Check(mid)) Ans=mid,l=mid+1;
        else r=mid-1;
    }
    while (l<=r);
    printf("%d\n",Ans);
    return 0;
}

bool Check(int mid)
{
    int mnsa=maxN,mxsa=0;
    for (int i=1;i<=n;i++)
        if (Height[i]>=mid)
        {
            mnsa=min(mnsa,SA[i]);
            mxsa=max(mxsa,SA[i]);
            if (mxsa-mnsa>=mid) return 1;
        }
        else mnsa=mxsa=SA[i];
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[hihocoder1407]后缀数组二·重复旋律2(后缀数组,二分)


HNCJ OIer