[hihocoder1403]后缀数组一·重复旋律(后缀数组,单调队列)

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


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

本文链接地址:[hihocoder1403]后缀数组一·重复旋律(后缀数组,单调队列)

Description

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。

小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。旋律是一段连续的数列,相似的旋律在原数列可重叠。比如在1 2 3 2 3 2 1 中 2 3 2 出现了两次。

小Hi想知道一段旋律中出现次数至少为K次的旋律最长是多少?

Tag

后缀数组

解决思路

提出所有的后缀后,相同旋律就是后缀中相同的前缀,那么出现次数为K就是要求重复了K次的相同前缀。
后缀数组求出Height后,问题转化为求连续的K个值的最小值中的最大值,这个可以用单调队列来维护。

代码

#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=20010;
const int inf=2147483647;

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

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>K;
    for (int i=1;i<=n;i++) cin>>Arr[i];
    //GetSA
    //初始化第一次排序的Rank
    mem(CntA,0);
    for (int i=1;i<=n;i++) CntA[Arr[i]]++;
    for (int i=1;i<=n;i++) CntA[i]+=CntA[i-1];
    for (int i=n;i>=1;i--) SA[CntA[Arr[i]]--]=i;
    Rank[SA[1]]=1;
    //倍增求解SA
    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<=n;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<=n;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]]++;
        }
    }
    //根据得到的SA和Rank构造出Height
    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=0;
    int Ans=0;
    for (int i=1;i<=n;i++)
    {
        while ((l<r)&&(Height[Queue[r]]>Height[i])) r--;
        Queue[++r]=i;
        if (i<=K-1) continue;
        while ((l<r)&&(Queue[l]+K-2<i)) l++;
        Ans=max(Ans,Height[Queue[l]]);
    }
    printf("%d\n",Ans);
    return 0;
}

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

本文链接地址:[hihocoder1403]后缀数组一·重复旋律(后缀数组,单调队列)


HNCJ OIer