[BZOJ4698/Luogu2463][SDOI2008]Sandy的卡片(差分,后缀数组,二分)

发布于 2018-03-25  97 次阅读


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

本文链接地址:[BZOJ4698/Luogu2463][SDOI2008]Sandy的卡片(差分,后缀数组,二分)

Description

Sandy和Sue的热衷于收集干脆面中的卡片。然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型,首先必须要集够N张卡片,对于这N张卡片,如果他们都有一个相同的子串长度为k,则可以兑换一个等级为k的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。Sandy的卡片数远远小于要求的N,于是Sue决定在Sandy的生日将自己的卡片送给Sandy,在Sue的帮助下,Sandy终于集够了N张卡片,但是,Sandy并不清楚他可以兑换到哪个等级的人物模型,现在,请你帮助Sandy和Sue,看看他们最高能够得到哪个等级的人物模型。

Tag

后缀数组,二分

题目大意

求若干字符串的最长公共子串

解决思路

把每一个数列差分一下,那么,原来对于相同的定义现在就转化为数列的相同子串问题。
把所有的差分数组连接起来,每两个之间用不同的分隔符隔开,求出后缀数组和Height后,二分这个最长公共子串的长度,假设为k,对于连续一段height大于k的,看是否所有的原数列都出现了一次,如果确实都出现了,则说明这个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=1001000;
const int dpos=1000;
const int inf=2147483647;

int n,m;
int L,Arr[maxN];
int Belong[maxN];
int SA[maxN],Rank[maxN],Height[maxN];
int CntA[maxN],CntB[maxN],A[maxN],B[maxN],SSA[maxN];
bool Appear[maxN];

bool Check(int l);

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        int m;cin>>m;
        int a;cin>>a;
        for (int j=2;j<=m;j++)//转化为差分数组并连接起来
        {
            int b;cin>>b;
            Arr[++L]=b-a+dpos;Belong[L]=i;a=b;//Belong[i]记录在连接起来的数组中位置在i的所属的是第几个卡片,方便后面二分判断
        }
        Arr[++L]=i+1000+dpos;//设置分隔符
    }
    //GetSA
    for (int i=1;i<=L;i++) CntA[Arr[i]]++;
    for (int i=1;i<maxN;i++) CntA[i]+=CntA[i-1];
    for (int i=L;i>=1;i--) SA[CntA[Arr[i]]--]=i;
    Rank[SA[1]]=1;
    for (int i=2;i<=L;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[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 (Arr[i+j]==Arr[SA[Rank[i]-1]+j]) j++;
        Height[Rank[i]]=j;
    }
    //二分最长公共子串长度
    int l=0,r=L;
    int Ans=0;
    do
    {
        int mid=(l+r)>>1;
        if (Check(mid)) Ans=mid,l=mid+1;
        else r=mid-1;
    }
    while (l<=r);
    cout<<Ans+1<<endl;//由于是差分,所以最后要加一
    return 0;
}

bool Check(int l)
{
    mem(Appear,0);Appear[0]=1;//Appear记录每一个原序列是否都出现了
    for (int i=1,cnt=0;i<=L;i++)
    {
        if (Height[i]>=l)//只统计Height大于当前二分的长度的
        {
            if (Appear[Belong[SA[i]]]==0) Appear[Belong[SA[i]]]=1,cnt++;
            if (Appear[Belong[SA[i-1]]]==0) Appear[Belong[SA[i-1]]]=1,cnt++;
            if (cnt==n) return 1;
        }
        else
        {
            if (cnt!=0) mem(Appear,0);
            cnt=0;Appear[0]=1;
        }
    }
    return 0;
}

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

本文链接地址:[BZOJ4698/Luogu2463][SDOI2008]Sandy的卡片(差分,后缀数组,二分)


HNCJ OIer