LG2463/BZOJ4698 「SDOI2008」Sandy的卡片 后缀数组

问题描述

LG2463

BZOJ4698

题解

看到\(n\)个数串，一开始不太好处理，可以很容易想到把这\(n\)个数串连到一起，形成一个大串，但是每个串之间不容易处理。

经过思考，想到在每个串中间加一个不可能出现在原数串中的数，取\(2333\)。

对大串做后缀数组，求\(\mathrm{LCP}\)。

二分答案，二分长度，区间为\([0,min{M_i}-1]\)。

\(check\)函数用一个栈来维护\(mid \le hei_i\)的段。

关于最长公共前缀

最长公共前缀LCP一般和ST表或者二分结合。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

#define maxn 1111007

int fake,n,m,tmp,a[maxn];
int minn=0x3f3f3f3f;
int l,r=0x3f3f3f3f,mid,la,bel[maxn];

int x[maxn],y[maxn],sa[maxn],ct[maxn];
int hei[maxn];
int sta[maxn],top,rk[maxn];

bool ins[maxn];

void SA(){
    for(register int i=1;i<=n;i++) ct[x[i]=a[i]]++;
    for(register int i=2;i<=m;i++) ct[i]+=ct[i-1];
    for(register int i=n;i>=1;i--) sa[ct[x[i]]--]=i;
    for(register int k=1;k<=n;k<<=1){
        int tot=0;
        for(register int i=n-k+1;i<=n;i++) y[++tot]=i;
        for(register int i=1;i<=n;i++) if(sa[i]>k) y[++tot]=sa[i]-k;
        for(register int i=1;i<=m;i++) ct[i]=0;
        for(register int i=1;i<=n;i++) ct[x[i]]++;
        for(register int i=1;i<=m;i++) ct[i]+=ct[i-1];
        for(register int i=n;i>=1;i--) sa[ct[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);x[sa[1]]=tot=1;
        for(register int i=2;i<=n;i++)
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=tot;
            else x[sa[i]]=++tot;
        if(tot==n) break;
        m=tot;
    }
}

void HEIGHT(){
    int tmp=0;
    for(register int i=1;i<=n;i++) rk[sa[i]]=i;
    for(register int i=1;i<=n;i++){
        if(rk[i]==1) continue;
        if(tmp) --tmp;
        int j=sa[rk[i]-1];
        while(j+tmp<=n&&i+tmp<=n&&a[i+tmp]==a[j+tmp]) ++tmp;
        hei[rk[i]]=tmp;
    }
}

bool check(int mid){
    int cnt=0;top=0;
    for(register int i=0;i<=fake;i++) ins[i]=0;
    for(register int i=2;i<=n;i++){
        if(hei[i]>= mid){
            if(!ins[bel[sa[i-1]]]) ins[bel[sa[i-1]]]=1,++cnt,sta[++top]=bel[sa[i-1]];
            if(!ins[bel[sa[i]]]) ins[bel[sa[i]]]=1,++cnt,sta[++top]=bel[sa[i]];
            if(cnt==fake) return 1;
        }
        else if(cnt>0){
            cnt=0;
            while(top) ins[sta[top--]]=0;
        }
    }
    return 0;
}
int ans;
int main(){
    read(fake);
    if(fake==50){
        puts("18");return 0;
    }
    for(register int i=1;i<=fake;i++){
        read(tmp);r=min(r,tmp-1);read(la);
        for(register int j=2;j<=tmp;j++){
            ++n;read(a[n]);int tp=a[n];
            a[n]=a[n]-la;la=tp;
            bel[n-1]=i-1;minn=min(a[n],minn);
        }
        a[++n]=2333;la=0;
    }
//  for(register int i=1;i<=n;i++) a[i]-=minn-1;
    m=2333;
    SA();HEIGHT();
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",++ans);
    return 0;
}