[hihocoder1415]后缀数组三·重复旋律3(后缀数组)

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


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

本文链接地址:[hihocoder1415]后缀数组三·重复旋律3(后缀数组)

Description

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。
旋律是一段连续的数列,如果同一段旋律在作品A和作品B中同时出现过,这段旋律就是A和B共同的部分,比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少?

Tag

后缀数组

解决思路

把两个字符串拼在一起求后缀数组,中间用一个其它的字符隔开。
构建出Height后,可以证明能够作为答案的一定是相邻两个后缀分属不同的字符串的答案,因为其它的分属不同字符串的后缀若要求lcp一定会跨越这些交界的Height,所以只需要求这些Height即可。

代码

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

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

const int maxN=100010*2;
const int inf=2147483647;

char Input1[maxN],Input2[maxN];
int str[maxN];
int SA[maxN],Rank[maxN],Height[maxN];
int Cnt1[maxN],Cnt2[maxN],A[maxN],B[maxN],SSA[maxN];

int main()
{
    ios::sync_with_stdio(false);
    cin>>(Input1+1);
    cin>>(Input2+1);
    int l1=strlen(Input1+1),l2=strlen(Input2+1);
    for (int i=1;i<=l1;i++) str[i]=Input1[i]-'a'+1;
    str[l1+1]='z'+1;
    for (int i=1;i<=l2;i++) str[i+l1+1]=Input2[i]-'a'+1;
    //构建SA
    int L=l1+l2+1;
    for (int i=1;i<=L;i++) Cnt1[str[i]]++;
    for (int i=1;i<maxN;i++) Cnt1[i]+=Cnt1[i-1];
    for (int i=L;i>=0;i--) SA[Cnt1[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(Cnt1,0);mem(Cnt2,0);
        for (int i=1;i<=L;i++)
        {
            Cnt1[A[i]=Rank[i]]++;
            Cnt2[B[i]=((i+l<=L)?(Rank[i+l]):(0))]++;
        }
        for (int i=1;i<maxN;i++) Cnt1[i]+=Cnt1[i-1],Cnt2[i]+=Cnt2[i-1];
        for (int i=L;i>=0;i--) SSA[Cnt2[B[i]]--]=i;
        for (int i=L;i>=0;i--) SA[Cnt1[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]]++;
        }
    }
    //构建Height
    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;
    }
    int Ans=0;
    for (int i=2;i<=L;i++)//统计跨越两个不同字符串后缀的Height的最大值
        if (((SA[i-1]<=l1)&&(SA[i]>=l1+1))||((SA[i-1]>=l1+1)&&(SA[i]<=l1))) Ans=max(Ans,Height[i]);
    cout<<Ans<<endl;
    return 0;
}

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

本文链接地址:[hihocoder1415]后缀数组三·重复旋律3(后缀数组)


HNCJ OIer