题解 P2463 【[SDOI2008]Sandy的卡片】

xMinh · 2018-03-26 09:24:22 · 题解

抵制mhr(@明月の卫——AH)暴力题解 从我做起！

SA多好啊

本题有多种解法 但是本蒟蒻只会后缀数组

关于后缀数组的详细讲解：

蒟蒻的博客

我们先把所有串连接在一起，用后缀数组求出LCP，然后二分长度，每次从头到尾扫一遍。

但是要注意连接的时候要加分割标记，这个只需要往两个串中间放一个大数就可以了。

根据LCP Theorem(证明过程见我博客)

LCP(i,k)=min(LCP(j,j-1)) 对于任意1<i<=j<=k<=n

设height[i]=LCP(i,i-1)

只要有n个>=len的height且其首字母属于不同的串就可以了

上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#define Big (1000000000 + 10)
#define maxn 111111
using namespace std;
int sa[maxn],rk[maxn],b[maxn],c[maxn],x[maxn],y[maxn];
int height[maxn],stack[maxn],id[maxn],len[1010],a[1010][1010];
int num,cnt,n,m,l,r,maxx,minn,ans,top;
bool vis[maxn]; 

int read() {
    char c=getchar();
    int r=0,f=1;
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        r=(r*10)+(c^48);
        c=getchar();
    }
    return r*f;
}

int min(int x,int y) {return x<y?x:y;}
int max(int x,int y) {return x>y?x:y;}

void Get_SA() {
    for (int i=1;i<=n;i++) ++c[x[i]=b[i]];
    for (int i=2;i<=m;i++) c[i]+=c[i-1];
    for (int i=n;i>=1;i--) sa[c[x[i]]--]=i;

    for (int k=1;k<=n;k<<=1) {
        cnt=0;
        for (int i=n-k+1;i<=n;i++) y[++cnt]=i;
        for (int i=1;i<=n;i++) if (sa[i]>k) y[++cnt]=sa[i]-k;

        for (int i=1;i<=m;i++) c[i]=0;
        for (int i=1;i<=n;i++) ++c[x[i]];
        for (int i=2;i<=m;i++) c[i]+=c[i-1];
        for (int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;

        swap(x,y);
        x[sa[1]]=1; cnt=1;
        for (int i=2;i<=n;i++) 
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?cnt:++cnt;
        if (cnt==n) break;
        m=cnt;
    }
}

void Get_Height() {
    int k=0;
    for (int i=1;i<=n;i++) rk[sa[i]]=i;
    for (int i=1;i<=n;i++) {
        if (rk[i]==1) continue;
        if (k) --k;
        int j=sa[rk[i]-1];
        while (j+k<=n && i+k<=n && b[i+k]==b[j+k]) ++k;
        height[rk[i]]=k;
    }
}

bool check(int x) {
    while (top) vis[stack[top--]]=0;
    for (int i=1;i<=n;i++) {
        if (height[i]<x) {
            while (top) vis[stack[top--]]=0;
        }
        if (!vis[id[sa[i]]]) {
            vis[id[sa[i]]]=1;
            stack[++top]=id[sa[i]];
            if (top==num) return 1; 
        }
    }
    return 0;
}

int main() {
    num=read(); 
    l=0;r=minn=Big;
    for (int i=1;i<=num;i++) {
        len[i]=read();
        for (int j=1;j<=len[i];j++) {
            a[i][j]=read();
            if (j!=1) maxx=max(maxx,a[i][j]-a[i][j-1]);
        }
        r=min(r,len[i]-1);
    }
    for (int i=1;i<=num;i++) {
        for (int j=2;j<=len[i];j++) {
            b[++n]=a[i][j]-a[i][j-1];
            id[n]=i;
            minn=min(minn,b[n]);
        }
        b[++n]=++maxx;
    }
    for (int i=1;i<=n;i++) {
        b[i]=b[i]-minn+1;
        m=max(m,b[i]);
    }
    Get_SA();
    Get_Height();
    while (l<=r) {
        int mid=(l+r)>>1;
        if (check(mid)) {
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    printf("%d",ans+1);
}