[hihocoder1419]后缀数组四·重复旋律4(后缀数组,ST表)

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


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

本文链接地址:[hihocoder1419]后缀数组四·重复旋律4(后缀数组,ST表)

Description

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为(k,l)-重复的,如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的,因为它由aba重复4次组成。
小Hi想知道一部作品中k最大的(k,l)-重复旋律。

Tag

后缀数组,ST表

解决思路

如果枚举长度l,再枚举一个位置pos,那么问题就变成询问两个后缀的lcp。这个可以在求出后缀数组后,求两个后缀对应之间的Height的最小值,而区间最小值可以用ST表求。
但如果枚举所有位置是不行的。考虑到循环重复串的性质,我们可以只枚举是l的倍数的地方的串查询lcp。
但这样若答案的开始的位置不在l的倍数的位置,就会有问题。但我们发现,在l的倍数的位置求出lcp能够帮助我们找到这个循环串的开头的位置,即当前位置-l+r%l,r为我们找到的lcp长度。那么在这个位置再求一次lcp即可。

代码

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

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

const int maxN=100100;
const int maxBit=18;
const int inf=2147483647;

char str[maxN];
int SA[maxN],Height[maxN],Rank[maxN];
int CntA[maxN],CntB[maxN],A[maxN],B[maxN],SSA[maxN];
int ST[maxN][maxBit];
int Log[maxN];

int Lcp(int p1,int p2);

int main()
{
    ios::sync_with_stdio(false);
    for (int i=1;i<maxN;i++) Log[i]=log2(i);

    cin>>(str+1);
    int L=strlen(str+1);
    //构造SA
    for (int i=1;i<=L;i++) CntA[str[i]]++;
    for (int i=1;i<maxN;i++) CntA[i]+=CntA[i-1];
    for (int i=L;i>=1;i--) SA[CntA[str[i]]--]=i;
    Rank[SA[1]]=1;
    for (int i=2;i<=L;i++)
    {
        Rank[SA[i]]=Rank[SA[i-1]];
        if (str[SA[i]]!=str[SA[i-1]]) Rank[SA[i]]++;
    }

    for (int l=1;Rank[SA[L]]<L;l=l<<1)
    {
        mem(CntA,0);mem(CntB,0);
        for (int i=1;i<=L;i++)
        {
            CntA[A[i]=Rank[i]]++;
            CntB[B[i]=((i+l<=L)?(Rank[i+l]):(0))]++;
        }
        for (int i=1;i<maxN;i++) CntA[i]+=CntA[i-1],CntB[i]+=CntB[i-1];
        for (int i=L;i>=1;i--) SSA[CntB[B[i]]--]=i;
        for (int i=L;i>=1;i--) SA[CntA[A[SSA[i]]]--]=SSA[i];
        Rank[SA[1]]=1;
        for (int i=2;i<=L;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<=L;i++)
    {
        if (j) j--;
        while (str[i+j]==str[SA[Rank[i]-1]+j]) j++;
        Height[Rank[i]]=j;
    }
    for (int i=1;i<=L;i++) ST[i][0]=Height[i];
    for (int i=1;i<maxBit;i++)
        for (int j=1;j<=L;j++)
            if (j+(1<<i)<=L)
                ST[j][i]=min(ST[j][i-1],ST[j+(1<<i)][i-1]);
    int Ans=0;
    for (int l=1;l<=L;l++)//枚举长度
        for (int i=1;i+l<=L;i+=l)//枚举位置
        {
            int r=Lcp(i,i+l);//先算直接从这一次位置开始的lcp
            Ans=max(Ans,r/l+1);
            //若能够向前移动到这一次重复串的实际开始,则在这个实际开始的位置再求一次
            if (i>=l-r%l) Ans=max(Ans,Lcp(i-l+r%l,i+r%l)/l+1);
        }
    cout<<Ans<<endl;
    return 0;
}

int Lcp(int p1,int p2)
{
    if (Rank[p1]>Rank[p2]) swap(p1,p2);
    p1=Rank[p1];p2=Rank[p2];
    p1++;
    int l=Log[p2-p1+1];
    return min(ST[p1][l],ST[p2-(1<<l)+1][l]);
}

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

本文链接地址:[hihocoder1419]后缀数组四·重复旋律4(后缀数组,ST表)


HNCJ OIer